题意：
有一群牛要上太空。他们计划建一个太空梯-----用一些石头垒。他们有K种不同类型的石头，每一种石头的高度为h_i，数量为c_i,并且由于会受到太空辐射，每一种石头不能超过这种石头的最大建造高度a_i。帮助这群牛建造一个最高的太空梯。

吐槽：

做练习的时候，连需不需要对数据排序都没分析清楚。。。下次再也不把练习安排在上午了，一般我上午状态极差（┬＿┬）

这题由于数据较水，可以直接把多重背包转化为01背包求解，当然由于设定的状态不一样，写法也会不一样滴。

Code1(01背包)：

 

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn=  410;int dp[40010];struct node {    int h, a, c;    bool operator <(const node& rhs) const {        return a< rhs.a;    }};node f[maxn];int main(){    int k, n, i, j, ans, maxa;    while(~scanf("%d",&n)) {        for(i=1; i<=n; i++) {            scanf("%d%d%d",&f[i].h,&f[i].a,&f[i].c);        }        sort(f+1,f+1+n);        memset(dp,0,sizeof(dp));        for(i=1; i<=n; i++) {            for(k=f[i].c; k>=1; k--){                for(j=f[i].a; j>=f[i].h; j--)                    dp[j] =max(dp[j], dp[j-f[i].h]+f[i].h);            }        }        maxa = 0;        for(j=f[n].a; j>=0; j--)            if(maxa 
      
     
    

 

Code(多重背包):

 

#include 
    
     #include 
     
      #include 
      
       #define  max(a,b)  a>b ? a:busing namespace std;const int maxn=  410;int dp[40010];struct node {    int h, a, c;    bool operator <(const node& rhs) const {        return a< rhs.a;    }};node f[maxn];void CompletePack(int C, int W, int V){    for(int i=C; i<=V; i++)        dp[i] = max(dp[i],dp[i-C]+W);}void ZeroOnePack(int C, int W, int V){    for(int i=V; i>=C; i--)        dp[i] = max(dp[i], dp[i-C]+W);}void MultipliePack(int C, int W, int M, int V){    if(C*M >=V) {        CompletePack(C,W,V);        return ;    }    int k=1;    while(k
       
        =0; i--)            if(maxH < dp[i]) maxH = dp[i];        printf("%d\n",maxH);    }    return 0;}