多重背包问题2
1. 问题描述
有N种物品和一个容量为V的背包。第i种物品最多有si件，每件体积是vi，价值是wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
1.1 输入格式
1
2
3
4
5
6
7
|
4 5
1 2 3
2 4 1
3 4 3
4 5 2
|
1.2 数据范围
- 0 < N ≤ 1000
- 0 < V ≤ 2000
- 0 < vi, wi, si ≤ 2000
2. 基本实现
2.1 朴素解法
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
| #include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N], s[N];
int dp[N][N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> s[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= m; j++) {
for(int k = 0; k <= s[i] && k * v[i] <= j; k++) {
dp[i][j] = max(dp[i][j], dp[i-1][j - k * v[i]] + k * w[i]);
}
}
}
cout << dp[n][m] << endl;
return 0;
}
|
2.2 一维数组优化
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
| #include <iostream>
using namespace std;
const int N = 2010;
int n, m;
int v[N], w[N], s[N];
int dp[N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> s[i];
}
for(int i = 1; i <= n; i++) {
for(int j = m; j >= 0; j--) {
for(int k = 1; k <= s[i] && k * v[i] <= j; k++) {
dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
cout << dp[m] << endl;
return 0;
}
|
3. 二进制优化
3.1 原理
将每种物品的数量si进行二进制拆分，转化为01背包问题。
3.2 实现代码
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
| #include <iostream>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N];
int dp[M];
int cnt;
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while(k <= s) {
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s > 0) {
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for(int i = 1; i <= n; i++) {
for(int j = m; j >= v[i]; j--) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[m] << endl;
return 0;
}
|
4. 单调队列优化
4.1 原理
利用单调队列优化转移方程，将时间复杂度降低。
4.2 实现代码
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
| #include <iostream>
using namespace std;
const int N = 20010;
int n, m;
int v[N], w[N], s[N];
int dp[N], g[N], q[N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i] >> s[i];
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < v[i]; j++) {
int head = 0, tail = -1;
for(int k = j; k <= m; k += v[i]) {
if(head <= tail && k - q[head] > s[i] * v[i]) head++;
while(head <= tail && g[q[tail]] <= g[k]) tail--;
q[++tail] = k;
g[k] = dp[k];
dp[k] = g[q[head]] + (k - q[head]) / v[i] * w[i];
}
}
}
cout << dp[m] << endl;
return 0;
}
|
5. 性能分析
5.1 时间复杂度
- 朴素解法: O(N * V * S)
- 二进制优化: O(N * V * logS)
- 单调队列优化: O(N * V)
5.2 空间复杂度
- 二维数组: O(N * V)
- 一维优化: O(V)
6. 实践建议
- 对于小规模数据，使用朴素解法即可
- 当物品数量较大时，使用二进制优化
- 当要求更高效率时，考虑单调队列优化
- 注意数组大小的定义，防止越界
7. 常见错误
- 数组开小导致越界
- 循环边界条件错误
- 二进制拆分时的处理错误
- 单调队列维护不当
8. 测试样例
1
2
3
4
5
6
7
8
9
|
4 5
1 2 3
2 4 1
3 4 3
4 5 2
10
|
