01背包和完全背包

01背包

每种东西只能放一次

#include<iostream>
using namespace std;
#define maxn 1001
int dp[maxn];
int volumn[maxn],weight[maxn];

int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>volumn[i]>>weight[i];
}

for(int i=1;i<=n;i++)//依次枚举每个物品
{
for(int j=m;j>=volumn[i];j--)
{
dp[j]=max(dp[j],dp[j-volumn[i]]+weight[i]);//判断放还是不放物品价值高
}
}
// for(int i=0;i<maxn;i++)
// cout<<dp[i]<<endl;//dp[i]表示背包容量为i时放东西的最大价值
cout<<dp[m]<<endl;//输出背包容量为m时东西的最大价值
}

测试数据

4 100
100 100
50 60
50 60
30 100

结果

160