AcWing 2. 01背包问题
原题链接
简单
作者:
Buctpeng
,
2023-10-01 14:01:19
,
所有人可见
,
阅读 52
另一种01背包dp的思想,我感觉更容易理解,很直接的表现出了状态转移过程.
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld",&x);
#define pr printf
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (-x&x)
const int N = 1110;
int f[N][N];//f[i][j]表示前i件物品重量小于等于j的时候的最大价值
int w[N];
int v[N];
int n,m;
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>w[i]>>v[i];
}
for(int i=1;i<=n;++i){
for(int j=0;j<=m;++j){
f[i][j] = max(f[i][j],f[i-1][j]);//不要第i件物品
if(j+w[i]<=m)
f[i][j+w[i]] = max(f[i][j+w[i]],f[i-1][j]+v[i]);//要第i件物品
}
}
cout<<f[n][m]<<endl;
}
signed main()
{
IOS
int t = 1;
//cin>>t;
while(t--) solve();
system("pause");
return 0;
}