背包问题

357

{% 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进行一遍循环即可

```cpp
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层的数据

因此,应该从前往后刷(正向刷表)


```cpp
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]);
发布评论
  • 点击查看/关闭被识别为广告的评论