/* 看到监狱兔 想起了朱晓凤,以前课间都是给我们放监狱兔看的,记忆犹新啊,不过后来老师走了。。。 题意:拥有金钱:m,鞋子分t种样式,每种样式必选一种,输出在<=m时的最大价值。 每组数据:样式sim,花费cost,获得价值:weight 分组背包 dp[i][k]=max(dp[i][k],max(dp[i][k-cost[j]]+weight[j],dp[i-1][k-cost[j]]+weight[j])); */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; #define INF -99999 int sim[105],cost[105],weight[105]; int dp[15][10005]; int main() { int i,j,k,n,m,t; while(scanf("%d%d%d",&n,&m,&t)!=EOF) { for(i=1; i<=n; i++) scanf("%d%d%d",&sim[i],&cost[i],&weight[i]); for(i=0; i<=t; i++) //初始化 for(j=0; j<=m; j++) { if(!i) dp[i][j]=0; // dp[i-1][k-cost[j]] 当i的1时,必须保证什么都没选时价值为0; else dp[i][j]=INF; } for(i=1; i<=t; i++) for(j=1; j<=n; j++) { for(k=m; k>=cost[j]; k--) { if(sim[j]==i) dp[i][k]=max(dp[i][k],max(dp[i][k-cost[j]]+weight[j],dp[i-1][k-cost[j]]+weight[j])); } } if(dp[t][m]<0) printf("Impossible\n"); else printf("%d\n",dp[t][m]); } return 0; }
原文:http://blog.csdn.net/littlefool5201314/article/details/23050513