fsdcyr 2015-06-08 02:42:28
点我顶贴
收藏
删除
dp[i][j]表示件数为i,体积为j 的背包所具有的最大价值,题目要求装满M件,初始化dp[0][0~L)=0,其余为-INF
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;
const int maxv = 1010;
int n,M,V;
int c[maxn],w[maxn];
int dp[maxn][maxv];
int main()
{
scanf("%d%d%d",&n,&M,&V);
for(int i=1;i<=n;++i){
scanf("%d%d",c+i,w+i);
}
for(int i=0;i<=n;++i){
for(int j=0;j<=V;++j){
if(i==0) dp[i][j]=0;
else dp[i][j]=-INF;
}
}
for(int i=1;i<=n;++i){
for(int j=M;j>=1;--j){
for(int k=V;k>=c[i];--k){
dp[j][k]=max(dp[j][k],dp[j-1][k-c[i]]+w[i]);
}
}
}
if(dp[M][V]<=0) puts("0");
else{
printf("%d\n",dp[M][V]);
}
return 0;
}