AcWing 2. 01背包问题
原题链接
简单
作者:
MeowRain
,
2024-02-21 13:38:09
,
所有人可见
,
阅读 29
#include <iostream>
using namespace std;
int n,t_capacity; // 物品数量和背包最大容量
const int N = 1010;
int volume[N],value[N]; //体积和价值
int dp[N][N]; //dp数组
int main() {
cin >> n >> t_capacity;
for(int i = 1;i<=n;i++ ) {
cin >> volume[i] >> value[i];
}
for(int i = 1;i<=n;i++) {
for(int j = 1;j<=t_capacity;j++) {//i表示第i个物品,j表示当前容量为j
if(j - volume[i] < 0) {
//当前背包容量装不下
//没有把这第 i 个物品装入背包,那么很显然,最大价值 dp[i][j] 应该等于 dp[i-1][j]
dp[i][j] = dp[i-1][j];
}else {
//如果能装下,就要讨论 把物品 i 装进背包,不把物品 i 装进背包这两种情况了
//不把物品i装进去,那就是dp[i - 1][j] ,放进去就是value[i] + dp[i-1][j - volume[i]]
dp[i][j] = max(dp[i-1][j],value[i] + dp[i-1][j - volume[i]]);
}
}
}
cout << dp[n][t_capacity];
}