题目描述
blablabla
样例
blablabla
C语言
算法1
/*
dp[i][j]:前i个物品在容量为j的情况存放的价值
选不了第i个物品: dp[i][j]=dpp[i-1][j];
能选:dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]+w[i]);
这就是dp的状态转移方程
*/
#include<stdio.h>
#define N 1010
int m,n;
int dp[N][N]; //dp[i][j]:前i个物品在容量为j的情况存放的价值
int v[N],w[N] ; //v[]:每个物品的体积,w[]每个物品的价值
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++) //遍历背包能放下的数量(dp[0][0]已经是0了,不管)
{
for(int j=0;j<=m;j++) // 遍历背包可能得容量(从0到m)
{
dp[i][j]=dp[i-1][j]; //先默认背包放不下第i个物品,所以当前价值和只能放i-1个物品一样
if(j>=v[i]) // 能放下第i个
{
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
}
}
int res=0;
for(int i=0;i<=m;i++) res=max(res,dp[n][i]); //从 n个物品找到价值最大的
printf("%d",res);
return 0;
}