[01背包问题.docVIP

01背包问题 一、问题描述 一个正在抢劫商店的小偷发现了n个商品，第i个商品价值Vi美元，重Wi磅，Vi和Wi都是整数；这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳W磅的商品，W是一个整数。 我们称这个问题是01背包问题，因为对每个商品，小偷要么把它完整拿走，要么把它留下；他不能只拿走一个商品的一部分，或者把一个商品拿走多次。 二、解决方案 背包问题作为NP完全问题，暂时不存在多项式时间算法动态规划（Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。 动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。 特征： 1、问题存在最优子结构 2、问题的最优解需要在子问题中作出选择 3、通过查表解决重叠子问题，避免重复计算 问题分析：令(i,j)表示在前i(≤in)个物品中能够装入为j(≤j≤W)的背包中的物品的最大价值，则可以得到如下的动态规划函数: f[i,j]=f[i-1,j] jwi ① f[i,j]=max{f[i-1,j] ,f[i-1,j-wi] +vi } jwi ② ①式表明：如果第i个物品的重量大于背包的，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；式表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-w的背包中的价值加上第i个物品的价值v; (b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解 时间复杂度为 伪代码： f[0,j]=0 For i=1 to n For j=0 to W f[i,j]=max{f[i-1,j] ,f[i-1,j-wi] +vi } return F[n,W] 问题的解为f[n,W] 代码实现: for(i=0;in;i++) for(j=0;j=W;j++)//j相当于上面说的-wi if(j=w[i]) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+val[i]);//放还是不放的选择 else [i][j]=f[i-1][j] C代码: #includeiostream # includecstring # define max(a,b) ab?a:b using namespace std; int main() { int dp[101][1001],m,T,w[101],val[101],i,j; cinTm; for(i=1;i=m;i++) cinw[i]val[i]; memset(dp,0,sizeof(dp)); for(i=1;i=m;i++) for(j=0;j=T;j++)//j相当于上面说的V-c[i] { if(j=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+val[i]);//放还是不放的选择 else dp[i][j]=dp[i-1][j]; } coutdp[m][T]endl; return 0; } 实例解析： 背包：容量10 3个物品： W1=3，V1=4 W2=4，V2=5 W3=5，V3=6 参考：/link?url=4f7wckWrL4AljAhbmwEJDlmPbIwaR5XyQSRGAA6gLppo-MoX_OEvrXREU1ohKReJhvrJWksG1HwLDfAhkyNp1nEhxvdwduxApQ8mAqvQHJ7 3.2回溯法 回溯法（探索与回溯法）是一种选优有哪些信誉好的足球投注网站法，按选优条件向前有哪些信誉好的足球投注网站，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通