问题：

有N种物品和一个容量为V的背包，每种物品都有无限件。 第i种物品的费用是w[i], 价值是c[i]。求解将哪些物品装入背包可使这些物品的总容量不超过背包容量，且总价值最大(优）

基本思路

该问题类似于01背包问题，所不同的是每种物品有无限件。 策略：取0件、取1件、… 取无限n

使用一维数组的伪代码：

for i = 1 .. N for v = 0 .. V f[v] = max{f[v],f[v-w[i]]+c[i]};

以上算法要求必须采用 v = 0 … V的正序顺序循环，这与01背包要求逆序不同。 为什么？每种物品可选无限件，所以在考虑“加选一件第i种物品”策略时，正需要一个可能已选入第i种物品的子结果f[i][v-w[i]]。所以必须采用正序。

二维数组动态转移方程： dp[i][v] = max{dp[i][v-w[i]] + c[i] , dp[i-1][v]}

题目描述

有n种物品，每种物品有一个重量和一个价值。但每种物品的数量是无限的，同时有一背包，最大载重量为m，今从n种物品中选取若干件（同一物品可以多次选取），使得重量（容量）的和小于等于m，而价值的和为最大。

输入格式

第 1 行：两个整数，M(背包容量，M<=200)和N(物品数量，N <=30);第 2 到 N+1行： 每行两个整数 Wi，Ci，表示每个物品的重量和价值。

输出格式

仅一行，一个数，表示最大总价值。

输入样例

10 4 2 1 3 3 4 5 7 8

输出样例

11

完全背包问题解法一

#include<bits/stdc++.h> using namespace std; /*完全背包问题（每种物品可选无限件） 设 dp[i][v]表示前i件物品，总容量不超过v的最优价值，则 dp[i][v]=max(dp[i-1][v],dp[i][v-w[i]]+c[i]) 说明：完全背包必须采用v = 0...M的正序顺序循环。 dp[i-1][v]: 当前物品i一个也不装 ，则总价值采用前i-1件物品，总容量不超v的最优价值。 dp[i][v-w[i]]+c[i]：加选一件当前物品i时， 正需要累加一个可能已选入第i件物品的子 结果dp[i][v-w[i]] dp[N][M]即是最优解 */ const int maxm=201, maxn =31;//maxm为容量 int m,n; int w[maxn],c[maxn]; int dp[maxn][maxm]; int main() { scanf("%d%d ",&m, &n);//背包容量m和物品数量n for(int i=1; i<=n;i++) scanf("%d%d",&w[i],&c[i]); //dp[i][v]表示前i件物品，总重量不超过v的最优价值 for(int i=1;i <= n; i++) for(int v=1;v <= m; v++) if(v< w[i]) dp[i][v]=dp[i-1][v]; else if(dp[i-1][v] > dp[i][v-w[i]]+c[i]) dp[i][v]=dp[i-1][v]; else dp[i][v] = dp[i][v-w[i]] + c[i]; printf(" max = %d",dp[n][m]);//最优解 return 0; }

完全背包空间O(V)解法二

//完全背包-一维数组解法 /* dp(v)表示容量不超过v公斤的最大价值，则 dp(v)= max{dp(v),dp(v-w[i])+c[i]} (v>=w[i], 1<=i<=n) */ #include<bits/stdc++.h> using namespace std; const int maxm =2001 , maxn =31; int n,m,v,i; int c[maxn],w[maxn]; int dp[maxm];//滚动数组压缩二维数组，转换成一维，减少空间成本 int main() { cin >> m >> n;//背包容量m ，物品数量(种类)n ，每种有无限个 for(i=1;i <= n; i++) cin>> w[i] >> c[i]; for(i =1 ; i <= n; i++) for(v=w[i];v<=m;v++ )//设dp[v]表示重量不超过v公斤的最大价值 dp[v]=max(dp[v],dp[v-w[i]]+c[i]); //与当前dp[v]内记忆的最优价值比较，谁优取谁 printf("max = %d\n",dp[m]);//f[m]为最优解 return 0; }

可能的优化

完全背包有一个简单有效的优化： 若两种物品i，j 满足 w[i] <= w[j] 同时 c[i] >= c[j] ，则将物品j去掉，不用考虑之。 正确性证明： 任何情况下都可将价值小，容量大的j换成性价比高的i，得到的方案至少不会更差。缺点：不能改善最坏情况的复杂度。

转化为01背包问题求解： 考虑第i种物品最多选 V/w[i]件，于是可以把第i种物品转化为 V/w[i]件重量及价值均不变的物品，然后求解这个01背包问题。 原理： 将一种物品拆成多件物品。

考虑把每种物品拆成O(log(V/w[i]）+ 1)件物品。 运用二进制思想，例如: 7（0111） == 2^0 + 2 ^ 1 + 2 ^ 2 k 来自集合{0,1,2} 对应拆分集合{ 1,2,4} 不管最优策略选几件第i种物品，总可以表示成若干个 2^k件物品的和。 高效拆分法： 把第i种物品拆成费用为 w[i] * 2^k , 价值为 c[i] * 2^k 的若干件物品，其中k满足w[i] * 2^k < V 。