错误代码:(至多是j)

初始化:memset(dp,0,sizeof(dp));
答案:dp[n][sums]

正确代码:(刚好是j)

初始化:memset(dp,0x3f,sizeof(dp));
答案:for(int j=0;j<=sumj;j++)ans=max(ans,dp[n][j]);

原因

以前能算到至多是 j 是因为dp[0][j]都是0，即从i=0时从哪个体积开始都是合法的，相当于把空余的体积加在了最前面，但现在这样不是最优,把空余时间加在最后面和最前面不一样。

总体思路

背包问题是不考虑顺序的(默认i的前一个是i-1),但这里要考虑顺序。
但是最优解的顺序是固定的(按$\frac{s_i}{l_i}$升序排列),所以此时只需要考虑选l哪些就行了。

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int M=105;
struct node{
    int s,e,l;
    #define s(i) a[i].s
    #define e(i) a[i].e
    #define l(i) a[i].l
    friend bool operator<(const node &x,const node &y){return x.s*y.l<y.s*x.l;}
}a[M];
int dp[M][M*M];
int main(){
    int t,n;scanf("%d",&t);
    for(int idxt=1;idxt<=t;idxt++){
        scanf("%d",&n);
        memset(dp,0,sizeof(dp));
        int sums=0;
        for(int i=1;i<=n;i++)scanf("%d%d%d",&s(i),&e(i),&l(i)),sums+=s(i);
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            for(int j=0;j<=sums;j++){
                if(j<s(i))dp[i][j]=dp[i-1][j];
                else dp[i][j]=max(dp[i-1][j],dp[i-1][j-s(i)]+max(0,e(i)-l(i)*(j-s(i))));
            }
        }
        int ans=0;
        for(int j=0;j<=sums;j++)ans=max(ans,dp[n][j]);
        printf("Case #%d: %d\n",idxt,ans);
    }
    return 0;
}