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
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int M,N;
cin>>M>>N;
int W[N],C[N];+_
int dp[N][M+1];
//接收
for (int i = 0; i < N; ++i) {
cin>>W[i]>>C[i];
}
//初始化
for (int i = 0; i < N; ++i) {
dp[i][0]=0;
}
for (int i = 1; i < M+1; ++i) {
if (W[0]<=i)dp[0][i]=C[0];
else dp[0][i]=0;
}
//dp
for (int i = 1; i < N; ++i) {
for (int j = 0; j < M+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]] + C[i]);
}
}
}
// for (int i = 0; i < N; ++i) {
// for (int j = 0; j < M+1 ;++j) {
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }

cout<<dp[N-1][M];
return 0;
}

dp[i][j] 表示从下标为 0 ~ i 的物品里任意取,放进容量为 j 的背包,价值总和最大是多少。

每次放进一个物品,每次增加一个背包容量,当物品放不进背包(j<W[i])时,取放进物品前的最好值(即dp[i-1][j])。即在图中取上一格的值;

1
if (j<W[i]) { dp[i][j] = dp[i - 1][j]; }

当物品可以放进背包时,考虑放与不放。

  • 不放:价值取图中上一格的值(即dp[i-1][j])。
  • 放:价值取下面两者的和:
    • 该物品的价值(即C[i])。
    • 先放进该物品后剩余的背包空间([j - W[i])与 不放该物品情况([i - 1]) 下的值(dp[i - 1][j - W[i])。后者是先前计算好的最优值,所以整体肯定是最优解。
1
2
3
4
5
dp[i][j] = 
max(
dp[i - 1][j], //不放
dp[i - 1][j - W[i]] + C[i] //放
);

01背包问题小结
http://lafish.fun/0-1-knapsack/
作者
lafish
发布于
2022年4月21日
许可协议