背包问题

Posted on | | Visitors:

简介

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总量不超过V的前提下，总价值是否能达到W？它是在1978年由Merkel和Hellman提出的。

01背包

有N件物品（每件物品只有一个）和一个容量为V的背包，第i件物品占据容量为c[i]，价值是w[i]，求解将哪些物品放入背包可使价值之和最大。

暴力求解应该怎么做？列出N个物品的全排列，一共有2的N次方种排列，在符合条件的排列中选出价值和最大的，显然这种方式不可取。

假如我们定义一种状态f[i][v]表示前i件物品中恰好放入（不是全部放入）容量v的背包可以获得的最大价值。有状态转移方程：

f[i][v] = max { f[i][v] , f[i-1][v-c[i]] + w[i] }

伪代码：

1
2
3
4
5
6
7
8
定义: f[v] 表示容量为v的背包可以获得的最大价值
     c[i] 表示第i件物品占据的容量
     w[i] 表示第i件物品的价值
     N    表示物品件数
     V    表示背包容量
for i = 0...N
  for v = V...c[i]
      f[v] = max(f[v], f[v-c[i]] + w[i])

注意：f[]数组是从后往前更新的，因为每个物品只有一个。

完全背包

如果每个物品的数量没有限制。

方式和01背包相同，但 f[] 数组要从前往后更新。

伪代码：

1
2
3
for i = 0...N
  for v = c[i]...V
      f[v] = max(f[v], f[v-c[i]] + w[i])

多重背包

如果每个物品的数量大于1个，但是数量有限。

这种情况可以用前两种方法来处理吗？

当然可以。如果该物品的总容量大于V，那么直接按照完全背包来处理即可；如果该物品的总容量小于V，该怎么使用01背包来处理呢？

该物品有多少个，就使用多少次01背包吗？

可以是可以，但是这样效率太低了。比如说我们从一个集合中选一些数字来表示1~13之间的数，最容易想到的集合就是{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}。如果我们使用神奇的二进制位来分割13，可以得到一个集合{1, 2, 4, 6}，这个集合和前面的那个效果一样，而且可以减少01背包的使用次数。

也就是任意C个物品都有：C = 1 + 2 … + 2 ^ (k - 1) + (C - 2^k + 1)。

然后对这些集合中的数做01背包处理。

伪代码：

1
2
3
4
5
6
7
k = 1
while (k < C) {
  执行01背包处理
  C -= k
  k *= 2
}
执行01背包处理

混合背包代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int sum;
int dp[101];
int max(int x,int y)
{
    return x>y?x:y;
}
void zeroonepack(int cost,int value)
{
    int i;
    for(i=sum;i>=cost;i--)
        dp[i]=max(dp[i],dp[i-cost]+value);
}
void completepack(int cost,int value)
{
    int i;
    for(i=cost;i<=sum;i++)
        dp[i]=max(dp[i],dp[i-cost]+value);
}
void multiplepack(int cost,int value,int amount)
{
    int k=1;
    if(cost*amount>=sum)
        completepack(cost,value);
    else
    {
        while(k<amount)
        {
            zeroonepack(k*cost,k*value);
            amount-=k;
            k*=2;
        }
        zeroonepack(amount*cost,amount*value);
    }  
}

int main(int argc, const char * argv[])
{
    int t;
    int n,a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&sum,&n);
        memset(dp,0,sizeof(dp));
        while(n--)
        {
            scanf("%d%d%d",&a,&b,&c);
            multiplepack(a,b,c);
        }
        printf("%d\n",dp[sum]);
    }
}

其他情况

如果背包不仅仅限制容量，还需要考虑重量怎么办呢？

答案是增加一个费用维度，a[i]表示第i件物品的重量，f[i][u][v]表示承重为u容量为v的背包在前i件物品中可以获取的最大价值，有状态转移方程：

f[i][u][v] = max { f[i][u][v], f[i-1][u-a[i]][v-c[i]] + w[i] }

如果物品之间还存在冲突关系，一组物品中只能拿一个又怎么处理呢？

做一个小小的变形即可，假设f[k][v]表示容量为v的背包在前k组物品中可以获得的最大价值，有状态转移方程：

f[k][v] = max { f[k][v], f[k-1][v - c[i]] + w[i]（i表示第k组中的第i件物品） }

伪代码：

1
2
3
4
for k (物品的组数)
  for v (这里根据背包种类确定遍历顺序)
    for i (第k组中的物品件数）
      f[v] = max(f[v], f[v-c[i]] + w[i])