poj2392(Space Elevator + 多重背包)

题目链接：http://poj.org/problem?id=2392

题意：有K种规格的楼梯，现在要用这K种规格的楼梯架高（就是一个楼梯一个接起来，变成一个更高的楼梯），但其中每种规格的楼梯有个限制，就是它的高度不能超过a(连接上它后楼梯的总高度不能超过a).现在告诉你这K种楼梯每种楼梯的高度为h,限制为a,有c个。问用这些楼梯最高能拼接成多高的楼梯。

首先要将这K种楼梯按限制a从小到大排序（不能清除解释，只好理解成常识了，莫见怪，呵呵。。），然后按照多重背包处理就Ok了。

代码：

#include<stdio.h>#include<string.h>#include<stdlib.h>struct Node{int h;int a;int c;}node[410];int K,ans;int dp[40005];int min(int a,int b){return a<b ? a : b;}int max(int a,int b){return a>b ? a : b;}int cmp(const void *x,const void *y){return (*(struct Node *)x).a-(*(struct Node *)y).a;}void ZeroOnePack(int cost,int V){ int v;     for(v=V;v>=cost;v--) { dp[v]=max(dp[v],dp[v-cost]+cost); }}void MultiplePack(int id,int amount){int k=1;while(k<amount){         ZeroOnePack(k*node[id].h,node[id].a); amount -= k; k *= 2;}    ZeroOnePack(amount*node[id].h,node[id].a);}int main(){int i;int minnum;while(scanf("%d",&K)!=EOF){for(i=0;i<K;i++)scanf("%d%d%d",&node[i].h,&node[i].a,&node[i].c);qsort(node,K,sizeof(struct Node),cmp);memset(dp,0,sizeof(dp));    for(i=0;i<K;i++){            minnum=min(node[i].c,node[i].a/node[i].h);MultiplePack(i,minnum);}ans =0;for(i=0;i<=node[K-1].a;i++)if(dp[i]>ans)ans = dp[i];printf("%d\n",ans);}return 0;}