网站名称及网址,如何注册网站平台,适合女人的小型加工厂,浙江省城乡建设监方网站一、问题描述
给定n种物品和一个背包。物品i的质量Wi#xff0c;其价值Vi#xff0c;背包的容量为c。问如何选择装入背包中的物品#xff0c;使得装入背包中的物品总价值最大#xff1f;
二、解题思想 01背包和最长公共子序列都是动态规划题目中求最优解的问题#xff0…一、问题描述
给定n种物品和一个背包。物品i的质量Wi其价值Vi背包的容量为c。问如何选择装入背包中的物品使得装入背包中的物品总价值最大
二、解题思想 01背包和最长公共子序列都是动态规划题目中求最优解的问题不同在于01背包问题即使发现物品可以放入背包但是在采取放或者不放的措施时还要进行选择。这就是保证最优解的条件 我们先根据题意有如下假设假设物品的种类和背包的容量是变化的是逐渐增多的。我们每个不同容量的背包的最大价值建立在先前背包最大价值的基础上。例如背包容量为5的最优解建立在背包容量为4的最优解的基础上。 既然容量和物品种类是变化的那么我们建立一个二维数组下文均称最佳价值表横向代表背包容量纵向代表物品种类将每个不同容量的背包的最优解记录在最佳价值表里这个最佳价值表记录的是满足题意的不同背包容量的最优解如下图所示。由此正式开始思解题算法思考递推式。 依照假设就会得出如下情况
A、当只有0种物品时无论背包的容量是多少背包内物品的总价值都为0因为没有东西可放当物品的种类很多时但是背包的容量为0背包内物品的总价值仍然为0因为放不进去啊所以这个最佳价值表的第0行第0列都是“0”其中V[0][0]0,不是因为我在程序中按照上述赋值为0其真实原因是只要是宏变量声明在头文件下的变量其初值都会自动为0。上述内容相当于对这个最佳价值表做了一个初始化如下图所示 B、当物品的种类和背包容量按照上图递增时就会又出现一种情况物品不能放入背包因为物品的质量大于当前背包可容纳的质量、物品能放入背包。
C、物品能放入背包也要分两种物品要放入、物品不放入。那么可能你要提问了为什么物品能装入但是却不选择装入呢
因为我们这个二维数组存储的是背包的最佳价值表。这个物品虽然能放到背包内但是如果它的体积过大放入后势必会影响后续的物品放入导致此最佳价值表违反了其“最佳”二字。如果第?个物品没有装入背包则背包中物品价值就等于把前?−1个物品装入容量为?的背包中所取得的价值; 如果把第?个物品装入背包则背包物品的价值等于第?−1个物品装入容量为?−weight[?]的背包中的价值加上第?个物品的价值value[?]。
综上
A、V[i][0]V[0][j]0 //简单初始化
B、V[i][j]V[i-1][j] //物品不能放入
C、V[i][j]max(v[i-1][j-weight[i]]value[i],v[i-1][j]) //物品能放入
表达式详细解析
看到这有的读者就会有很多问题我来以一问一答的形式让大家更加来了解这道题目的解题思想
Q1为什么表达式中每次用当前背包的总容量和新出现的物品的质量作比较而不是用背包剩余的容量与新出现的物品的质量作比较
A1这个问题也是我接触动态规划问题之初提过的一个问题。01背包是典型的动态规划问题既然是动态规划问题那么就要动起来整个问题中动就只有一个——物品放入背包中。你可以设想一下假设你在实际操作的时候虽然给出的物品很多但因为你目光有限所以看到的东西也是一个一个进入眼帘。你可能会先将一个物品放入背包但是因为后来出现了又小、价值又高的物品你在权衡之后可能又得把之前放入的这个物品掏出腾出空间来放当前这个质量小、价值高的物品·······说了这么多铺垫可能有的人已经明白了这道题的关注点只在于背包能放得下还是放不下而不是背包放进一些东西之后剩余的空间放的下还是放不下。这个其实直接可以从上述C的表达式可以看出即发现物品可放入的时候你需要以背包的总价值作为衡量依据到底是放入价值更高了此时有的人可能会问了难道物品放入背包后价值还会降低因为放入物品的时候需要腾出一定的空间这就需要拿出背包里的物品所以放入物品价值不一定更高还是不放价值更高了所以用一个max函数来比较。如果发现放入价值高那就得腾出空间用最佳价值表的纵轴坐标
Q2做这类问题的时候有什么秘诀没有
A21、既然是动态问题那么我们的大脑就得灵活而且得联系实际情况把大问题化成简单的小问题。计算机是一个很傻的处理机器重复做着相同的工作唯一的优点就是快我们需要做的事情就是告诉他应该做什么事情做的次数等其他的就不需要多想了。 2、第二点就是不要多想直接推导递推式然后求解就像Q1的那种问题就不要多加考虑了。
三、具体实现
#includestdio.h
#includestdlib.h
#includeiostream
using namespace std;
int V[100][100];//用来存储背包的最大价值
int weight[100]; //存储物品的重量
int value[100];//存储物品的价值
int state[100];//存储物品的选取状态
int max(int a,int b)//比较价值大小函数
{if (ab)return a;else return b;
}
int KnapSack(int n,int weight[],int value[],int state[],int capacity)//动态规划求解函数
{int i,j;//循环变量//V[0][0] 0;for (i1;in;i)//当j0时(j代表背包容量)0容量什么都装不进去所以V[i][j]0;V[i][0]0;for (j1;jcapacity;j)//当i0时代表没有物品即使背包容量再大其V[0][j]0;V[0][j]0;//#####下面进行判断######for (i1;in;i)//i代表物品j代表背包容量{//j代表背包的容量将其从0逐步增加到输入的背包容量相当于以背包的容量为限制一步一步求得最大价值的方法。for (j1;jcapacity;j){if(jweight[i])//表示该物品?不能装入背包。V[i][j]V[i-1][j];//表明此处的价值等于前i-1个物品装入的价值。else//第?个物品的重量小于背包的容量后就会有两种情况一种放入一种不放入求这两种情况中Value最大的。V[i][j]max(V[i-1][j],V[i-1][j-weight[i]]value[i]);//如果把第?个物品装入背包则背包物品的价值等于第?−1个物品装入容量位?−weight[?]的背包中的价值加上第?个物品的价值value[?]//如果第?个物品没有装入背包则背包中物品价值就等于把前?−1个物品装入容量为?的背包中所取得的价值。}}jcapacity;//为标记“哪件物品放入背包”做准备for(in;i1;i--)//标记选出的物品函数{if(V[i][j]V[i-1][j]){state[i]1;//1表示选中jj-weight[i];}elsestate[i]0;//0表示未选中}printf(选中的物品是:);for(i1;in;i)printf(%d ,state[i]);printf(\n);coutV[i][j]中的数字是\n;for(int i0;in;i){for(int j0; jcapacity;j){printf(%3d, V[i][j]);if (j capacity){printf(\n);}}}return V[n][capacity];
}
int main()
{int s;//获得的最大价值int n 0;//用于循环输入cout 请输入物品的个数;cin n;cout 请输入物品对应的质量;for (int i 1; i n; i)cin weight[i];cout 请输入物品对应的价值;for (int i 1; i n; i)cin value[i];cout 请输入背包最大容量;int capacity;cin capacity;//背包最大容量s KnapSack(n, weight, value, state, capacity);cout最大物品价值为:sendl;system(pause);return 0;
}
其中有一个for循环用来找出哪些东西被放入背包中1代表放入0代表没放入。 为了方便理解我来多贴几张图在这里就不做gif图了大家顺着我的这个图去理解。
函数种前两个for循环程序执行之后蓝色区域为最佳价值表区域 这个是只有物品1的时候 出现物品2其中绿色的6就是一个在比较之后填入的价值绿色的9是当前两个物品的总和。 按照函数中的算法一个一个模拟的把数字填写进去相信你就会理解这道题目了。
