题目描述

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

第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。

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

输入格式

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

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

输出格式

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

数据范围

$0 \lt N, V \le 1000$
$0 \lt v_i, w_i \le 1000$

输入样例

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

输出样例

1
10

题目分析

相比$01$背包问题，完全背包问题每件物品可以选择 无数次，状态转移方程变得更加复杂。对于$f[i][j]$仍然表示只选前$i$个物品总体积小于等于$j$的最佳方案。状态转移方程如下：

通过纯数学角度的分析对于$f[i][j-v]$展开有：

我们可以发现对于$(2)$和$(1)$中从第二项开始的项类似，彼此间只相差一个$w$，因此结合$(1)$和$(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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;

int f[N][N], v[N], w[N], n , m;


int main() {
    cin >> n >> m;
    for(int i = 1 ; i <= n ;i ++) {
        cin >> v[i] >> w[i];
    }
    
    for(int i = 1; i <= n; i ++) {
        for(int j = 0; j <= m ;j ++) {
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    }
    
    cout << f[n][m];
}

滚动数组优化

由状态转移方程可以知道，$f[i][j] = max(f[i-1][j], f[i][j-v]+w)$，f[i][j]是依赖于f[i][j-v]，因此完全背包问题需要从前往后进行计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;

int f[N], v[N], w[N], n , m;


int main() {
    cin >> n >> m;
    for(int i = 1 ; i <= n ;i ++) {
        cin >> v[i] >> w[i];
    }
    
    for(int i = 1; i <= n; i ++)
        for(int j = v[i]; j <= m ;j ++) 
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        
    cout << f[m];
}