转自：()
完全背包是在N种物品中选取若干件（同一种物品可多次选取）放在空间为V的背包里，每种物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解怎么装物品可使背包里物品总价值最大。 动态规划（DP）： 1） 子问题定义：F[i][j]表示前i种物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。 2） 根据第i种物品放多少件进行决策 (2-1) 其中F[i-1][j-K*C[i]]+K*W[i]表示前i-1种物品中选取若干件物品放入剩余空间为j-K*C[i]的背包中所能得到的最大价值加上k件第i种物品； 设物品种数为N，背包容量为V，第i种物品体积为C[i]，第i种物品价值为W[i]。f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v} 举例：表2-1为一个背包问题数据表，设背包容量为10根据上述解决方法可得到对应的F[i][j]如表2-2所示，最大价值即为F[6][10].
表2-1背包问题数据表物号i 1 2 3 4 5 6体积C 3 2 5 1 6 4价值W 6 5 10 2 16 8表2-2前i件物品选若干件放入空间为j的背包中得到的最大价值表 0 1 2 3 4 5 6 7 8 9 100 0 0 0 0 0 0 0 0 0 0 01 0 0 0 6 6 6 12 12 12 18 182 0 0 5 6 10 11 15 16 20 21 253 0 0 5 6 10 11 15 16 20 21 254 0 2 5 7 10 12 15 17 20 22 255 0 2 5 7 10 12 16 18 21 23 266 0 2 5 7 10 12 16 18 21 23 26
解释1 具体背包中放入那些物品的求法和01背包情况差不多，从F[N][V]逆着走向F[0][0]，设i=N,j=V，如果F[i][j]==F[i][j-C[i]]+W[i]说明包里面有第i件物品，同时j -= C[i]。完全背包问题在处理i自减和01背包不同，01背包是不管F[i][j]与F[i-1][j-C[i]]+W[i]相不相等i都要减1，因为01背包的第i件物品要么放要么不放，不管放还是不放其已经遍历过了，需要继续往下遍历而完全背包只有当F[i][j]与F[i-1][j]相等时i才自减1。因为F[i][j]=F[i-1][j]说明背包里面不会含有i，也就是说对于前i种物品容量为j的背包全部都放入前i-1种物品才能实现价值最大化，或者直白的理解为前i种物品中第i种物品物不美价不廉，直接被筛选掉。
同样可以转换成一维数组来表示：for i=1..N for v=0..V f[v]=max{f[v],f[v-c[i]]+w[i]} 顺序
想必大家看出了和01背包的区别，这里的内循环是顺序的，而01背包是逆序的。
现在关键的是考虑：为何完全背包可以这么写？ 在次我们先来回忆下，01背包逆序的原因？是为了是max中的两项是前一状态值，这就对了。 那么这里，我们顺序写，这里的max中的两项当然就是当前状态的值了，为何？ 因为每种背包都是无限的。当我们把i从1到N循环时，f[v]表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。 这里同样给大家一道题目：() 思路：多重背包和以上两种的不同点在于，多重背包给了具体的重量，价钱，数量，可以转换为01背包求解(代码1)，也可以进行二进制优化,将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,…,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。例如，如果n[i]为13，就将这种 物品分成系数分别为1,2,4,6的四件物品，这种方法有模板（代码2），这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为O(V*Σlog n[i])的01背包问题，是很大的改进，还有楼天城的单调队列法，表示不会。。。代码#include#include using namespace std;#include #define mem(a,b) memset(a,b,sizeof(a));#define INF 0x3fffffffint v[50005],w[10005];int f[10005];int main(){ int t; scanf("%d",&t); while(t--) { mem(v,0); mem(w,0); mem(f,0); int E,F; scanf("%d%d",&E,&F); int c=F-E; for(int i=1; i<=c; i++) { f[i]=INF; } int u; scanf("%d",&u); for(int i=1; i<=u; i++) { int n,m; scanf("%d%d",&n,&m); v[i]=n; w[i]=m; } for(int i=1; i<=u; i++) { for(int j=w[i]; j<=c; j++) { f[j]=min(f[j],f[j-w[i]]+v[i]); } } if(f[c]==INF) printf("This is impossible.\n"); else printf("The minimum amount of money in the piggy-bank is %d.\n",f[c]); } return 0;}
因为三个背包加在一起太长，我都看不下去了，换个地方，
01背包： 多重背包：