题目链接
对于01背包,我也理解的感觉也不上特别透彻
下面是核心代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
//#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 1005;
int dp[N][N] = {0};
signed main () {
int n, m;
scanf("%d %d", &n, &m);
int v[N], w[N];
for (int i = 1; i <= n; i++) {
scanf("%d %d", &v[i], &w[i]);
}
//i表示这个背包可以装前i个物品,j表示这个背包的最大容量,dp[i][j]的值为这个背包所能装下的最大的价值
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {//将这个背包分解成n*m个背包,
if (v[i] > j) {//如果当前背包的重量不能放入当前这个物品
dp[i][j] = dp[i - 1][j];//所以这个背包转换为可以装前i-1个物品,容量为j的背包
} else {
//如果当前的背包可以放下当前的物品
//dp[i-1][j],这个背包是不取第i个物品
//dp[i-1][j-v[i]],这个背包是取出第i个物品
//最后取这两个的最大值
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
cout << dp[n][m] << '\n';//通过dp数组直接得出结果
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
// }
//}
return 0;
}