01背包

每件物品只能使用一次

01背包的理解

引用自b站的评论

二维解法:

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

using namespace std;
//二维解法

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

int main() {
int n, weight;
scanf("%d%d", &n, &weight);

for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);

for (int i = 1; i <= n; i++)
for (int j = weight; j >= 1; j--)
if (j < w[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

cout << dp[n][weight] << endl;
}

优化后:

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

using namespace std;
//一维解法

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

int main() {
int n, weight;
scanf("%d%d", &n, &weight);

for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);

for (int i = 1; i <= n; i++)
for (int j = weight; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

cout << dp[weight];
}

先遍历物品的解法:

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

using namespace std;
//先遍历物品,再遍历容量

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

int main() {
int n, weight;
scanf("%d%d", &n, &weight);

for (int i = 1; i <= n; i++)
scanf("%d%d", &w[i], &v[i]);

for (int i = 1; i <= weight; i++)
for (int j = 1; j <= n; j++)
if (i - w[j] < 0) dp[j][i] = dp[j - 1][i];
else dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - w[j]] + v[j]);
cout << dp[n][weight];
}

01背包
http://example.com/2022/07/09/01背包/
作者
Charry
发布于
2022年7月9日
许可协议