大意
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<cstdio> #include<algorithm> 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<arr[i].c;k++) for(int j=arr[i].a;j>=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 ",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<cstdio> #include<cstring> #include<algorithm> 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++) scanf("%d%d%d",&arr[i].h,&arr[i].a,&arr[i].c); sort(arr,arr+n,cmp); memset(dp,-1,sizeof(dp)); dp[0] = 0; 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 ",ans); return 0; }