{% blockquote 百度百科——背包问题%}
**背包问题(Knapsack problem)**是一种组合优化的NP完全问题。
问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学,计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题,即在总重量不超过W的前提下,总价值是否能达到V?它是在1978年由Merkel和Hellman提出的。
{% endblockquote %}
在背包问题里,有很著名的《背包九讲》来帮助我们理解背包问题。
下载:《背包九讲》
01背包问题
条件:
- 背包大小V
- 物品件数n(每个物体只有1个)
- 第i个物品的花费c[i]
- 第i个物品的价值w[i]
即在保证花费和不超过V的情况下,尽可能让价值最大(有的题目中花费就是价值)
用dp[i][j]
表示前i个物品在最大体积为j的情况下的最大价值(所求答案为dp[n][V]
)
对于第i个物品,我们可以选择“选”( dp[i-1][ j-c[i] ] + w[i]
)或“不选”(dp[i-1][ j ]
)
有dp[i][j] = max{ dp[i-1][j] , dp[i-1][j - c[i]] + w[i] }
当从i=1开始循环时,在计算dp[i][]
时,dp[i-1][]
已经计算过了,因此我们可以算出所有的值
同时,可以发现我们计算dp[i][j]
之会用到dp[i-1][j]
和dp[i-1][j-c[i]]
并且 j>j-c[i]
如图,可以将二维数组降为一维数组,只要保证比当前计算的dp[i][j]
的j小的还停留在“上一层”(i-1)即可
也即从后往前刷(逆序刷表)
并且可以知道可能更新的的最小的值为dp[i][c[i]
] (当剩余空间比c[i]
还小时,j-c[i]
不在合法范围内)
因此,可以写出如下代码
void ZeroOnePack(int cost,int weight) { for (int i = v; i >= cost; i--) dp[i] = max(dp[i],dp[i - cost] + weight); }
使用时只需从i=1到i=n进行一遍循环即可
for(int i=1;i <= n;i++) ZeroOnePack(c[i],w[i]);
初始时要将dp[0][]初始化为0
完全背包问题
条件:
背包大小V
-
物品件数n(每个物体有无数个)
-
第i个物品的花费c[i]
-
第i个物品的价值w[i]
即在保证花费和不超过V的情况下,尽可能让价值最大(有的题目中花费就是价值)
用dp[i][j]
表示前i个物品在最大体积为j的情况下的最大价值(所求答案为dp[n][V]
)
对于第i个物品,我们可以选择“不选”(dp[i-1][j]
) 或 “选1个”( dp[i-1][ j-c[i] ] + w[i]
) 或 “选2个”( dp[i-1][ j- 2*c[i] ] + 2*w[i]
) ……
有dp[i][j] = max{ dp[i][j] , dp[i-1][j - k*c[i]] + k*w[i] } (0<=k<=∞ 当 j - k*c[i] <= 0 时结束循环)
由于dp[i][j]
已经是选出来的最大值了,在计算dp[i][j+cost[i]]
时,只需比较dp[i][j]
和dp[i-1][j+c[i]]+w[i]
也即dp[i][j]=max{ dp[i][j-c[i]]+w[i] , dp[i-1][j] }
可以看出来,我们计算dp[i][j]
时,需要的是不大于j的i层的数据
因此,应该从前往后刷(正向刷表)
void CompletePack(int cost,int weight) { for (int i = cost; i <= v; i++) dp[i] = max(dp[i],dp[i - cost] + weight); }
同上,使用时只需循环1-n即可
for(int i=1;i <= n;i++) ComplatePack(c[i],w[i]);
多重背包问题
条件:
- 背包大小V
- 物品件数n(每个物体有无数个)
- 第i个物品的花费c[i]
- 第i个物品的价值w[i]
- 第i个物品的上限max[i]
即在保证花费和不超过V的情况下,尽可能让价值最大(有的题目中花费就是价值)
用dp[i][j]
表示前i个物品在最大体积为j的情况下的最大价值(所求答案为dp[n][V]
)
有dp[i][j] = max{ dp[i-1][ j - k * D[i] ] + k * D[i] , dp[i][j] } (0 <= k <= max[i])
此时,时间复杂度为O(V*∑n[i])
采用二进制分解可以优化到O(V*∑log n[i])
对于数量为0-n的物品i,可以将其分割成多个组合。
使得所有组合加起来能够等于n,并且选取一定量的组合可以组成0-n的任意数
例如13可以分解成1、2、4、6
0=0
1=1
2=2
3=1+2
4=4
5=1+4
6=2+4
7=1+2+4
8=2+6
9=1+2+6
10=4+6
11=1+4+6
12=2+4+6
13=1+2+4+6
一个数可以分成两个数,两个数相加可以得到这个数
而这两个数还能继续分成两个数
…………
如果分成的两个数相等,则可以再下次分割只分其中一个
这样在保证尽可能少分的情况下分到最深就是需要的计算方法
这样,对于一个最多有n个的物品,可以分成(近似)log(2)n个,然后对这些进行01背包求解
如果物品i的总体积大于背包体积,则不必再分割(在范围内没有上限可以看作无限)。
使用完全背包求解
void MultiplePack(int cost,int weight,int n) { if (cost * n > v) { CompletePack(cost,weight); } else { int k = 1; while (k < n) { ZeroOnePack(cost * k,weight * k); n -= k; k *= 2; } ZeroOnePack(cost * n,weight * n); } }
计算时需要
for(int i=1;i <= n;i++) MultiplePack(c[i],w[i],max[i]);