01背包模板题
描述
你有一个背包，最大容量为 V。现有 n 件物品，第 i 件物品的体积为 v[ i ]，价值为 w[ i ]。研究人员提出以下两种装填方案：
1. 1. 不要求装满背包，求能获得的最大总价值；
2. 2. 要求最终恰好装满背包，求能获得的最大总价值。若不存在使背包恰好装满的装法，则答案记为 0。
输入描述：
第一行输入两个整数 nn 和 V(1≦n,V≦103)V(1≦n,V≦103)，分别表示物品数量与背包容量。
此后 nn 行，第 ii 行输入两个整数 vi,wi(1≦vi,wi≦103)v**i,w**i(1≦v**i,w**i≦103)，分别表示第 ii 件物品的体积与价值。
输出描述：
输出两行：
1. 1. 第一行输出方案 1 的答案；
2. 2. 第二行输出方案 2 的答案（若无解输出 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include <cstring>
using namespace std;
const int N = 1005;
int n, V;
int v[N], w[N];
int dp[N][N];
int main() {
cin >> n >> V;
for (int i = 0; i < n; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i - 1]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
}
}
cout << dp[n][V] << endl;
memset(dp, 0, sizeof(dp));
for (int j = 1; j <= V; j++)
dp[0][j] = -1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i - 1] && dp[i - 1][j - v[i - 1]] != -1) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
}
}
if (dp[n][V] == -1)
cout << 0 << endl;
else cout << dp[n][V] << endl;
return 0;
}
|
完全背包模板题
描述
你有一个背包，最多能容纳的体积是V。
现在有n种物品，每种物品有任意多个，第 i 种物品的体积为v[ i ] ,价值为w[ i ]。
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？
输入描述：
第一行两个整数n和V，表示物品个数和背包体积。
接下来n行，每行两个数v[ i ]和w[ i ]。，表示第 i 种物品的体积和价值。
1≤n,V≤10001≤n,V≤1000
输出描述：
输出有两行，第一行输出第一问的答案，第二行输出第二问的答案，如果无解请输出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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
const int N = 1005;
int n, V;
int w[N];
int v[N];
int dp[N];
int main() {
cin >> n >> V;
for (int i = 1 ; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (j - v[i] >= 0) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
cout << dp[V] << endl;
memset(dp, 0, sizeof dp);
for (int j = 1; j <= V; j++) {
dp[j] = -1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= V; j++) {
if (j - v[i] >= 0 && dp[j - v[i]] != -1) {
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
cout << ((dp[V] == -1) ? 0 : dp[V]) << endl;
return 0;
}
|