大意

n件物品，第i件hi高，有ci件，最高的一件不能超过ai的高度。问最高能堆多高输入第一行，一个n 

接下来每一行，为hi，ai，ci输出最高堆多高样例

输入

　　3 

　　7 40 3 

　　5 23 8

　　2 52 6

样例输出

　　48 

（从下到上：3个2号，3个1号，6个3号）

 

多重背包

 

这是bool 数组记录能否到达的代码 200ms

 

#include
      
       #include
       
        using namespace std;struct s{    int h, a, c;}arr[405];bool cmp(s a, s b){    if(a.a != b.a)        return a.a < b.a;    return a.h < b.h;}bool dp[40105];int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d%d%d",&arr[i].h,&arr[i].a,&arr[i].c);    sort(arr+1,arr+n+1,cmp);    dp[0] = true;    for(int i=1;i<=n;i++){        for(int k=0;k
        
         =0;j--){            if(j>=arr[i].h)                dp[j] = dp[j] || dp[j] || dp[j-arr[i].h];            else                dp[j] = dp[j] || dp[j];        }    }    int ans = 0;    for(int i=0;i<40105;i++)        if(dp[i])ans = i;    printf("%d\n",ans);    return 0;}
        
       
      

 

但是，可以进行优化。

定义dp[j] 表示 高度为 j 的堆剩余的第 i 件物品的个数。

那么， 在第 i 次循环中 如果 dp[j] 不为 -1 那就意味着 j 可以被 第 i 件物品构建出来（不论是用光了还是没用上）

所以第 i 件物品没有用上（构建 j 时）

转移表达式为 dp[j] := arr[i].c （第 i 件物品的初始数量）

 

如果 dp[j] == -1 那也就是说之前的 i-1 件物品没能构建出 j ，那我们就用 j - arr[i].h 这一堆加上一件 arr[i] 就可以构建出 j 了

判断一下 dp[ j - arr[i].h ] 是否被构建了 同时考虑好边界和细节就好了

转移表达式为 dp[j] := dp[j-arr[i].h] - 1

 

这是优化后的 int 数组记录第i件物品剩余个数的代码 47ms

 

#include
      
       #include
       
        #include
        
         using namespace std;struct s{    int h, a, c;}arr[405];bool cmp(s a, s b){    if(a.a != b.a)        return a.a < b.a;    return a.h < b.h;}int dp[40105];int main(){    int n;    scanf("%d",&n);    for(int i=0;i
         
          < n;i++){        for(int j=0;j <= arr[i].a;j++){            if(dp[j] >= 0)                dp[j] = arr[i].c;            else if(j >= arr[i].h && dp[j-arr[i].h] > 0)                dp[j] = dp[j - arr[i].h] - 1;        }    }    int ans = 0;    for(int i=0;i<=arr[n-1].a;i++)        if(dp[i] >= 0)ans = i;    printf("%d\n",ans);    return 0;}