一、问题描述：
完全背包：有n种物品和容量为v的背包，每种都有无限的物品。 第I件物品的费用为c[i]，价值为w[i]。 求出将哪些物品放入背包，这些物品的费用合计不会超过背包的容量，且价值合计最大。
多重背包：有n种物品和容量为v的背包。 第I件物品最多可使用n[i]件，每件费用为c[i]，价值为w[i]。 求出将哪些物品放入背包，这些物品的费用合计不会超过背包的容量，且价值合计最大。
如果你想看到这两个主题和我上次提到的0-1背包(0-1背包，请试着移动到0-1背包)。 不同之处在于每个背包类型的数量。 01每个背包只有一个，每个完整背包无限个，但每个多重背包有限个。
二、完全背包动态规划过程：
根据放入多少个第I个物品来决定，所以状态转移方程式
其中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]。
和01背包一样，完全背包也需要求出NV个状态F[i][j]。 但是，在将F[i][j]完全背包求出的情况下，需要对k分别取0，…，j/C[i]来求出最大的F[i][j]值。
因此，代码必须是三层循环(项目数、项目类型和背包大小三个循环)。 伪代码如下。
f [0]{0} f [ ]{0} I ]() ) )
经过考虑，我认为完整的背包可以转换为0.1背包：
因为可以多次选择相同的，所以第I个最多可以选择V/C[i]的价值不变的，转换为0.1背包问题。 将第I个物品分解为体积为C[i]2k的价值W[i]2k的物品，其中满足C[i]2kV。 即，假设F[i][j]显示了通过从最初的I种物品中选择几个物品放入容量j的背包中而获得的最大价值。 中，对于第I个项目的出现，决定是否将第I个项目放入背包。 那么F[i][j]=F[i-1][j]； 如果确定放进去，背包里应该至少会出现一个第I类物品。 因此，F[i][j]种应该至少出现一个第I种物品。 即F[i][j]=F[i][j-C[i]] W[i]。 为什么要变成F[i][j-C[i]] W[i]？ 因为F[i][j-C[i]]可能包含或不包含第I个项目。 我们必须确保F[i][j]至少有一个第I个物品，所以必须留出C[i]的空间保管一个第I个物品。
状态方程式如下。
0-1背包和完全背包的区别：
从二维阵列中区分0-1背包和完全背包(即状态转移方程)放入第I个行李时，完全背包选择放入此行李时，最优解为F[i][j-c[i]] w[i]，即表中同行的一方
从一维数组中区分0-1背包和完全背包的区别就是循环顺序。 0-1背包必须逆序。 这可以确保不重复选择选定的项目，但完全背包是顺序的，顺序涵盖以前的状态，因此可能会多次选择，也符合完全背包的题意。 状态转移方程均为f[I]=max(f[I]，DP[f-c[I] ) v[I] )。
三、完全背包代码
一维数组实现
# include cstdio # includealgorithmusingnamespacestd； int w[300]、c[300]、f[300010]； int V，n； int main () Scanf ) ' %d%d '，v，n )； for(intI=1； i=n； I ) scanf('%d%d '，w[i]，c[i]； }for(intI=1； i=n； I ) for(intj=w[I]； j=V； j(//注意这里，与0-1背包不同，这里是顺序，0-1背包是逆序f[j]=max(f[j]，f[j-w[I] ) c[I] ) ) ) 返回0； }多重背包问题的想法与完全背包的想法非常相似，但k的可取值有限。 因为，每个东西
品的数量是有限制的，状态转移方程为：dp[i][v] = max{dp[i - 1][v - k * c[i]] + w[i] | 0 <=k <= n[i]}
其中c[i]是物品的数量，和完全背包的不同支出在于完全背包可以取无数件，而多重背包给定了最多能取的数量。这样也是三个循环，分别是背包容量，物品个数和物品种类。这样如果数量比较多的情况，很明显这个做法也会超时，所以我们也要想更优化的方法去完善。
转化为01背包问题转化为01背包求解：把第i种物品换成n[i]件01背包中的物品。考虑二进制的思想，考虑把第i种物品换成若干件物品，使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。另外，取超过n[i]件的策略必不能出现。
方法是：将第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的四件物品。
分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，证明我也没看过这里就不贴上了，主要还是需要去理解代码，代码在下面给出。
五、多重背包代码：
#include <stdio.h>#include <iostream>#include <algorithm>#include <cstring>#define MAX 1000000using namespace std;int dp[MAX];//存储最后背包最大能存多少int value[MAX],weight[MAX],number[MAX];//分别存的是物品的价值，每一个的重量以及数量int bag;void ZeroOnePack(int weight,int value )//01背包{ int i; for(i = bag; i>=weight; i--) { dp[i] = max(dp[i],dp[i-weight]+value); }}void CompletePack(int weight,int value)//完全背包{ int i; for(i = weight; i<=bag; i++) { dp[i] = max(dp[i],dp[i-weight]+value); }}void MultiplePack(int weight,int value,int number)//多重背包{ if(bag<=number*weight)//如果总容量比这个物品的容量要小，那么这个物品可以直到取完，相当于完全背包 { CompletePack(weight,value); return ; } else//否则就将多重背包转化为01背包 { int k = 1; while(k<=number) { ZeroOnePack(k*weight,k*value); number = number-k; k = 2*k;//这里采用二进制思想 } ZeroOnePack(number*weight,number*value); }}int main(){ int n; while(~scanf("%d%d",&bag,&n)) { int i,sum=0; for(i = 0; i<n; i++) { scanf("%d",&number[i]);//输入数量 scanf("%d",&value[i]);//输入价值 此题没有物品的重量，可以理解为体积和价值相等 } memset(dp,0,sizeof(dp)); for(i = 0; i<n; i++) { MultiplePack(value[i],value[i],number[i]);//调用多重背包,注意穿参的时候分别是重量，价值和数量 } cout<<dp[bag]<<endl; } return 0;}