网站营销外包,cfensi.wordpress,开发公司抽奖送房,网站开发最新架构学习交流加 个人qq#xff1a; 1126137994个人微信#xff1a; liu1126137994学习交流资源分享qq群#xff1a; 962535112 一个背包有一定的承重cap#xff0c;有N件物品#xff0c;每件都有自己的价值#xff0c;记录在数组v中#xff0c;也都有自己的重量#xff0c;… 学习交流加 个人qq 1126137994个人微信 liu1126137994学习交流资源分享qq群 962535112 一个背包有一定的承重cap有N件物品每件都有自己的价值记录在数组v中也都有自己的重量记录在数组w中每件物品只能选择要装入背包还是不装入背包要求在不超过背包承重的前提下选出物品的总价值最大。
给定物品的重量w价值v及物品数n和承重cap。请返回最大总价值。
测试样例 [1,2,3],[1,2,3],3,6 返回6
这个背包问题还是很不好理解的其实
解题思路 假设物品编号为1~n一件一件考虑是否装入背包内。有两个变量w代表各个物品的重量数组和v代表各个物品的价值数组。同样还是开辟一个新的空间大小为dp[n][cap],那么dp[i][j]代表前i件物品且背包承重为j时的物品最大价值那么dp[n][cap]就是我们的最终所求即矩阵的最右下角
求解步骤 1、求第一行 dp[0][j]代表前0件物品的价值都为0所以dp[0][j]0 2、求第一列 dp[j][0]代表前j件物品但是背包的承重为0所以总价值也是都为0所以dp[i][0]0 3、求其他行 dp[i][j]代表前i件物品背包的承重为j时所能获得的最大价值。可以分为以下两种情况 一拿第i件物品 拿第i件物品的时候首先要保证条件判断第i件物品的重量w[i-1]注意这里为什么是i-1因为数组w是从0号开始它的0号对应的是矩阵第一列的1号当矩阵的为i时对应的w里应该是i-1不能超过j(超过j就不会拿第i件产品了)。而当我们拿了第i件物品后前i-1件的物品获得的最大价值也会重新分布有可能会减少此时到底是拿第i件物品后价值大还是不拿第i件物品产品大呢这个是不确定的所以需要去判断选择. 1拿的话价值应该等于 v[i-1]第i件物品的价值为什么是i-1原因与w[i-1]一样加上前i-1件物品背包承重j-w[i-1]的价值 2不拿的话价值就直接等于dp[i-1][j] 然后选择上述的较大值就行 此时
if(jw[i-1])dp[i][j] max(dp[i-1][j],v[i-1]dp[i-1][j-w[i-1]])二不拿第i件物品 当我想拿第i件物品时如果w[i-1]j,就不能拿因为一拿就超过背包的承重。所以此时的价值就直接等于前i-1件物品背包承重i时的价值 即
if(jw[i-1])dp[i][j] dp[i-1][j];最终的代码如下 运行通过了所有的测试用例
class Backpack {
public:int maxValue(vectorint w, vectorint v, int n, int cap) {// write code hereint dp[n1][cap1];//初始化一列for(int i0;in1;i)dp[i][0]0;//初始化第一行for(int j0;jcap1;j)dp[0][j]0;//求其他行的值 for(int i1;in1;i){for(int j1;jcap1;j){//拿第i件物品,拿了后的总价值不一定比不拿前的总价值高因为拿了第i件物品后前面的i-1件物品的分配汇会改变if((j-w[i-1])0)dp[i][j]max(v[i-1]dp[i-1][j-w[i-1]],dp[i-1][j]);//不拿第i件物品elsedp[i][j]dp[i-1][j]; }}return dp[n][cap];}
};
