POJ 2392 Space Elevator 0-1背包
来源：http://poj.org/problem?id=2392
题意：有一些种类的砖块，其中每种砖块的高度和数量给了，而且每种砖块都有一个限制条件，就是说以该种砖块结束的最大高度H不能超过某个高度，不同砖块的该高度不同。求最高的高度是多少。
思路：由于每种砖块的高度H限制了取得砖块数，而且也决定了砖块放的顺序。因此，先对砖块的种类按照H的高度从小到达排序，之后对每种砖块按照0-1背包处理就行了
代码：
#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>using namespace std;#define CLR(arr,val) memset(arr,val,sizeof(arr))const int N = 410;struct blocks{int height,totalheight,num;}bb[N];int dp[N*100],pos;bool cmp(blocks a,blocks b){return a.totalheight < b.totalheight;}int min(int a,int b){return a<b?a:b;}int max(int a,int b){return a>b?a:b;}void one_zero_bag(int id,int cnt){int k = 1;while(k < cnt){for(int v = bb[id].totalheight;v >= 0;--v){if(v >= k*bb[id].height){dp[v] = max(dp[v],dp[v - k*bb[id].height] + k*bb[id].height);}}cnt -= k;k *= 2;}for(int v = bb[id].totalheight;v >= 0;--v){if(v >= cnt*bb[id].height){dp[v] = max(dp[v],dp[v - cnt*bb[id].height] + cnt*bb[id].height);}}}int main(){//freopen("1.txt","r",stdin);int n;while(scanf("%d",&n) != EOF){for(int i = 0;i < n;++i)scanf("%d%d%d",&bb[i].height,&bb[i].totalheight,&bb[i].num);sort(bb,bb+n,cmp);CLR(dp,0);pos = 0;for(int i = 0;i < n;++i){int minnum = min(bb[i].num,bb[i].totalheight/bb[i].height);one_zero_bag(i,minnum);pos = dp[bb[i].totalheight];}int mmax = 0;for(int i = 0;i <= bb[n-1].totalheight;++i)if(mmax < dp[i])mmax = dp[i];printf("%d\n",mmax);}return 0;}