AcWing 2. 01背包问题
原题链接
简单
作者:
逸误
,
2023-07-15 21:46:36
,
所有人可见
,
阅读 64
#include <iostream>
using namespace std;
const int N = 1005;
int n,m;
int v[N],w[N];//v体积,w价值
int dp[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
}//第0列刚好都是0,不用初始化
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)//m代指题中的V
{
if(j<v[i]) dp[i][j]=dp[i-1][j];
else dp[i][j]=max(dp[i-1][j],w[i]+dp[i-1][j-v[i]]);
}
cout<<dp[n][m]<<endl;
return 0;
}
#include <iostream>
using namespace std;
const int N = 1005;
int n,m;
int v[N],w[N];//v体积,w价值
int dp[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&v[i],&w[i]);
}//第0列刚好都是0,不用初始化
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--) //在同一列中逆序,防止前面的数据被“污染”
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
cout<<dp[m]<<endl;
return 0;
}