算法学习014 0-1背包问题 c++动态规划算法实现 中小学算法思维学习 信奥算法解析

本文主要是介绍算法学习014 0-1背包问题 c++动态规划算法实现 中小学算法思维学习 信奥算法解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

C++0-1背包

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、运行结果

五、考点分析

六、推荐资料


C++0-1背包

一、题目要求

1、编程实现

有 N 件物品和一个容量为 M的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。

2、输入输出

输入描述:第一行输入两个整数,分别表示N和M,中间空格隔开

                  第二行输入N个整数,表示每件物品需要的空间(vi)

                  第三行输入N个整数,表示每件物品的价值(wi)

输出描述:只有一行,一个整数,即最大的价值总和

输入样例:

4 20
8 9 5 2
5 6 7 3

输出样例:

16

二、算法分析

  1. 从给定题目的初步分析可以看出,本题是比较典型的背包问题
  2. 所以可以采用动态规划的方式实现
  3. 由于要求的是最大价值总和,所以可以设置动态数组dp[i][j],i表示第i个物品,j表示放入物品的容量,dp[i][j]表示的是放入前i个物品,且容量不超过j的最大价值
  4. 而每件物品可以选择放或者不放,如果不放,也就是前i-1件物品放入容量为j的背包,对应的dp[i][j] = dp[i-1][j]
  5. 如果放入i件物品,也就是前i-1件物品,也就是前i-1件物品放入容量为j-vi的背包的价值总和,加上当前第i件物品对应的价值wi,dp[i][j] = dp[i-1][j-v[i]] + w[i]
  6. 所以可以得出对应的动态数组dp[i]的状态转移方为:dp[i]=max(dp[i-1][j],dp[i-1][j-v[i]] + w[i])
  7. 物品放入背包是逐个放置,所以遍历顺序从前往后

三、程序编写

解法一:

//程序中的dp和cost数组可以使用动态数组vector进行实现更好
//N为物品数量,m为最大容量,dp存放的是前i件物品容量为j所能获得的最大价值
//v数组存放的是每件物品所需空间,w数组为每件物品对应的价值
#include<iostream>
using namespace std;
const int N = 101;
const int M = 100000;
int dp[N][M],v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin >> v[i];for(int i=1;i<=n;i++)cin >> w[i];for(int i=1;i<=n;i++)for(int j=0;j<=m;j++){if(j>v[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);else dp[i][j] = dp[i-1][j];}cout << dp[n][m];
}

解法二:(优化)

//0-1背包
//N为物品数量,m为最大容量,dp存放的是前i件物品容量为v所能获得的最大价值
//v数组存放的是每件物品所需空间,w数组为每件物品对应的价值
#include<iostream>
using namespace std;
const int N = 101;
const int V = 100010;
int dp[V],v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin >> v[i];for(int i=1;i<=n;i++)cin >> w[i];for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--){dp[j] = max(dp[j],dp[j-v[i]]+w[i]);}cout << dp[m];
}

 本文作者:小兔子编程 作者首页:小兔子编程-CSDN博客

四、运行结果

8
2 3 2 3 2 3 1 27

五、考点分析

难度级别:中等,这题相对而言在于背包容量和最大值,具体主要考查如下:

  1. 分析题目,找到解题思路
  2. 充分掌握变量和数组的定义和使用
  3. 学会动态规划算法的原理和使用
  4. 确定动态数组的定义和含义
  5. 分析出动态规划算法的状态转移方程以及遍历顺序
  6. 学会输入流对象cin的使用,从键盘读入相应的数据
  7. 学会for循环的使用,在确定循环次数的时候推荐使用学会
  8. 掌握输出流对象cout的使用,与流插入运算符 << 结合使用将对象输出到终端显示
  9. 学会分析题目,算法分析,将复杂问题模块化,简单化,从中找到相应的解题思路
  10. 充分掌握变量定义和使用、分支语句、循环语句和动态规划算法的应用

PS:方式方法有多种,小朋友们只要能够达到题目要求即可!

六、推荐资料

  • 所有考级比赛学习相关资料合集【推荐收藏】

这篇关于算法学习014 0-1背包问题 c++动态规划算法实现 中小学算法思维学习 信奥算法解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1087269

相关文章

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代