POJ 2392 Space Elevator 0-1双肩包

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;
}