题目

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi，wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 < N, V ≤ 10000 < N, V ≤ 1000
0 < vi, wi ≤ 10000 < vi, wi ≤ 1000

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例

1
10

朴素写法

分析

状态转移方程

  • 不装第 i 件物品：dp[i][j] = dp[i - 1][j]
  • 装 k 个第 i 件物品：dp[i][j] = dp[i - 1][j - K * v[i]] + k * w[i]

合起来就是dp[i][j] = dp[i - 1][j - K * v[i]] + k * w[i] (0 <= k * v[i] <= j)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int v[N], w[N];
int dp[N][N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
            for(int k = 0; k * v[i] <= j; k++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + w[i] * k);
                
    printf("%d", dp[n][m]);
    
    return 0;
}

初步优化

思路

首先我们来看一下dp[i][j] = dp[i - 1][j - k * v[i]] + k * w[i]这个式子（用 v代替 v[i]，w代替 w[i]）

1
2
3
4
5
6
dp[i][j] = max(dp[i-1][j], dp[i-1][j-v]+w, dp[i-1][j-2v]+2w,...)
dp[i][j-v] = max(          dp[i-1][j-v],   dp[i-1][j-2v]+w,...)
    
根据上面两个式子，可以得到关系: dp[i][j] = dp[i][j - v] + w
    即dp[i][j]可以用这一层的上一个状态再装一件 i 得到
由此可得状态转移方程：dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])

举例

用一个具体例子来辅助理解（题目数据）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
v[1] = 1, w[1] = 2
v[2] = 2, w[2] = 4
v[3] = 3, w[3] = 4
v[4] = 4, w[4] = 5
    
dp[1][1] = max(dp[0][1] == 0, dp[1][0] + w[1] == 2) == 2
dp[1][2] = max(dp[0][2] == 0, dp[1][1] + w[1] == 4) == 4
dp[1][3] = max(dp[0][3] == 0, dp[1][2] + w[1] == 6) == 6
dp[1][4] = max(dp[0][4] == 0, dp[1][3] + w[1] == 8) == 8
dp[1][5] = max(dp[0][5] == 0, dp[1][4] + w[1] == 10) == 10	// dp[1][5]由dp[1][4]再装v[1]得到

dp[2][2] = max(dp[1][2] == 4, dp[2][0] + w[2] == 4) == 4
dp[2][3] = max(dp[1][3] == 6, dp[2][1] + w[2] == 6) == 6
dp[2][4] = max(dp[1][4] == 8, dp[2][2] + w[2] == 8) == 8
dp[2][5] = max(dp[1][5] == 10, dp[2][3] + w[2] == 10) == 10	// dp[2][5]由dp[2][3]再装v[2]得到

dp[3][3] = max(dp[2][3] == 6, dp[3][0] + w[3] == 4) == 6
dp[3][4] = max(dp[2][4] == 8, dp[3][1] + w[3] == 6) == 8
dp[3][5] = max(dp[2][5] == 10, dp[3][2] + w[3] == 8) == 10

dp[4][4] = max(dp[3][4] == 8, dp[4][0] + w[4] == 5) == 8
dp[4][5] = max(dp[3][5] == 10, dp[4][1] + w[4] == 7) == 10

初步优化结果

有了上面的方程，那么 k 循环就可以不要了

1
2
3
4
5
for(int i = 1; i <= n; i++)
    for(int j = 0; j <= m; j++) {
        dp[i][j] = dp[i - 1][j];
        if(v[i] <= j) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
    }

与01背包比较

这个和 01 背包像，我们来比较一下：

1
2
01背包:  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])
完全背包：dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])

再次优化

因为和01背包很像，所以我们很容易想到进一步的优化：

1
2
3
for(int i = 1; i <= n; i++)
    for(int j = v[i]; j <= m; j++)	// 这里不需要倒叙
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

为什么不需要倒叙呢？

我们上一篇讲到01背包的状态转移方程需要的是上一轮的状态值，所以不能先更新状态值

而完全背包需要的是本轮中上一步的状态值，所以需要从小到大遍历，先更新状态值

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int v[N], w[N];
int dp[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);
    
    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= m; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
                
    printf("%d", dp[m]);
    
    return 0;
}