动态规划(五)——背包问题_背包问题时间复杂度

问题

背包问题的变体很多，这里主要分析三个类型：0-1背包，完全背包和多重背包。

0-1背包

问题

有n件物品，每件物品有各自的重量和价值，现有一个一定容量的背包，问如何选择使背包物品价值最大

分析

• 最基础的方法是枚举，但时间复杂度为$O(2^2)$
• 动态规划的可以将时间复杂度降为$O(nm)$
  • 设置一个二维数组dp[][],令dp[i][j]表示前i个物品装进容量为j的背包能获得的最大价值,则dp[n][m]就是问题的解
  • 对于容量为j的背包，如果不放入第i件物品，那么这个问题就转换成将前i-1物品放入容量为j的背包的问题，即dp[i][j]=dp[i-1][j]
  • 对于容量为j的背包，如果放入第i件物品，那么当前背包的容量就变成了j-w[i],并得到这个物品的价值v[i]。之后这个问题就转化成将前i-1个物品放入容量为j-w[i]的背包的问题，即dp[i][j]=dp[i-1][j-w[i]]+v[i]。
  • 综上所述，可以得到状态转移方程dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
  • 考虑边界条件dp[i][0]=dp[0][j]=0(0<=i<=n,0<=j<=m)
  • 可以看到状态转换方程中第i行数据至于i-1行数据有关，所以可以将二维数组优化为一维数组，只保存上一行的数据，则状态转换方程变为dp[j] = max(dp[j],dp[j-w[i]]+v[i])
  • 为了保证状态转换的正确，需要倒序遍历所有j值，才能保证dp[j-w[i]]尚未被修改

例题

描述
北大网络实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为C元，有N种菜可以点，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为Vi，每种菜的价格为Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。 注意：由于需要营养多样化，每种菜只能点一次。
输入描述：
输入的第一行有两个整数C（1 <= C <= 1000）和N（1 <= N <= 100），C代表总共能够报销的额度，N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的的整数，分别表示菜的>价格和菜的评价分数。
输出描述：
输出只包括一行，这一行只包含一个整数，表示在报销额度范围内，所点的菜得到的最大评价分数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main(int argc, char const *argv[])
{
    int m, n; //m:容量，n：物品数量
    while (scanf("%d%d", &m, &n) != EOF)
    {
        int weight[n], value[n], dp[m + 1];
        for (int i = 0; i < n; i++)
            scanf("%d%d", &weight[i], &value[i]);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
        	//倒序遍历j,当j<weight[i]显然是装不下的,所以是不会装进去,也就是dp[j]不变
        	//较二维数组存储,也一定程度简化了在装不下第i个物品的处理
            for (int j = m; j >= weight[i]; j--)
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        printf("%d\n", dp[m]);
    }
    return 0;
}

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

完全背包

问题

对0-1背包问题的拓展，如果每个物品可以取多件时，如何选择使得价值最大

分析

也是采用动态规划时间复杂度为$O(nm)$

• 设置一个二维数组dp[][],令dp[i][j]表示前i个物品装进容量为j的背包能获得的最大价值,则dp[n][m]就是问题的解
• 对于容量为j的背包，如果不放入第i件物品，那么这个问题就转换成将前i-1物品放入容量为j的背包的问题，即dp[i][j]=dp[i-1][j]
• 对于容量为j的背包，如果放入第i件物品，那么当前背包的容量就变成了j-w[i],并得到这个物品的价值v[i]。但由于第i件物品还是可以取，所以状态转换到dp[i][j-w[i]]
• 综上所述，可以得到状态转移方程dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i])
• 考虑边界条件dp[i][0]=dp[0][j]=0(0<=i<=n,0<=j<=m)
• 也可以优化为一维数组,以为仅与当前行和上一行的状态相关，则状态转换方程可化为dp[j] = max(dp[j],dp[j-w[i]]+v[i])
• 为了保证状态转化的正确，需要保证在确定dp[j]时,dp[j-w[i]]已经完成了本次更新,所以需要正序遍历所有j值

例题

描述
向存钱罐里投各种硬币,每种硬币有自己的面值和重量,现在我们已知所有硬币的总重量和各种硬币的面值和重量,求问这些硬币的最小价值是多少.
输入描述：
第一行输入为T,表示输入有T个测试用例;
每个测试用例的开头是两个数字E,F($1\le E\le F\le 10000$),分别表示存钱罐空时的重量和测算时的重量;
接下来一行是硬币的种类数目N($1\le N\le 500$);
接下来的N行,每行有两个数字P,W($1\le P\le 50000,1\le W\le 10000$)构成,分别是硬币的面值和重量
输出描述：
如果可以估计出最小价值则输出该价值X,否则输出This is impossible

输入样例:

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2 
10 3
20 4
1
2
3
4
5
6
7
8
9
10
11
12
13

分析

• 这里求得是最小值,所以需要修改状态方程为dp[j] = min(dp[j],dp[j-w[i]]+v[i])
• 要求重量恰好达到总重量,也就是背包恰好装满,将dp[0]初始化为0,将dp[i]初始化为无穷大

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 10000
//这里不能使用INT_MAX,实际测试时会出现-INT_MAX值,在计算过程中超出界限
#define INF INT_MAX/10
using namespace std;
int weight[MAXN], value[MAXN], dp[MAXN];

int main(int argc, char const *argv[])
{
    int caseNumber;
    scanf("%d", &caseNumber);

    while (caseNumber--)
    {
        int e, f;
        scanf("%d%d", &e, &f);
        int m = f - e; // 硬币得总重量
        int n;
        scanf("%d",&n);
        
        for (int i = 0; i < n; i++)
            scanf("%d%d", &weight[i], &value[i]);

        //初始化dp
        dp[0] = 0;
        for (int i = 1; i < m; i++)
        {
            dp[i] = INF;
        }

        for (int i = 0; i < n; i++)
            for (int j = weight[i]; j <= m; j++)
                dp[j] = min(dp[j], dp[j - weight[i]] + value[i]);
        if (dp[m] == INF)
        {
            printf("This is impossible\n");
        }
        else
        {
            printf("%d\n", dp[m]);
        }
    }
    return 0;
}
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

多重背包

问题

再次拓展，如果每个物品可以取多件时，但最多取$k_i$件，如何选择使得价值最大

分析

• 将每种物品均视为k种质量和价值都相同的不同物品，对所有物品求0-1背包问题，时间复杂度为$O(m{\sum }_{i=0}^n{k}_i)$
• 如果降低$k_i$会降低时间复杂度，可以对物品进行如下拆分：将原有数量为k的物品拆分成若干组，每组物品视作一件物品，其价值和重量为该组中所有物品的价值重量总和。每组物品包含的个数分别为$2^0,2^1,...,2^c,k-2^{c+1}+1$,其中c是使得$k-2^{c+1}+1\ge 0$的最大整数
• 上述分法可以通过不同的组合得到0到k之间的任意件物品的价值重量和，时间复杂度降为$O(m{\sum }_{i=0}^{n}lo{g}_2(k_i))$

例题

描述
现共有资金n元,市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买.问做多能买多多少千克的大米
输入描述：
第一行输入为T,表示输入有T个测试用例;
每个测试用例的开头是两个数字n,m($1\le n\le 100,1\le m\le 100$),分别表示经费的金额和大米的种类
接下来的m行,每行有3个数字p,h,c($1\le p\le 20,1\le h\le 200,1\le c\le 20$)构成,分别每袋大米的价格,质量和对应种类大米的袋数
输出描述：
输出能购买的最大大米质量

输入样例:

1
8 2
2 100 4
4 100 2
1
2
3
4

#include <iostream>
#include <cstdio>
#define MAXN 10000

using namespace std;

int dp[MAXN];
int v[MAXN];      // 原物品价值
int w[MAXN];      // 原物品重量
int k[MAXN];      // 原物品数量
int value[MAXN];  // 拆分后物品价值
int weight[MAXN]; // 拆分后物品重量

int main(int argc, char const *argv[])
{
    int caseNumber;
    scanf("%d", &caseNumber);
    while (caseNumber--)
    {
        int n, m;
        scanf("%d%d", &m, &n);
        int number = 0;

        for (int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &w[i], &v[i], &k[i]);
            // 分解物品
            // 2^0,..
            for (int j = 1; j <= k[i]; j <<= 1)
            {
                value[number] = j * v[i];
                weight[number] = j * w[i];
                number++;
                k[i] -= j;
            }
            //k-2^(c+1)+1
            if (k[i] > 0)
            {
                value[number] = k[i] * v[i];
                weight[number] = k[i] * w[i];
                number++;
            }
        }

        for (int i = 0; i <= m; i++)
            dp[i] = 0;
        for (int i = 0; i < number; i++)
            for (int j = m; j >= weight[i]; j--)
            	// 状态转换
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        printf("%d\n", dp[m]);
    }
    return 0;
}

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