我要没做过清仓甩卖还真不会这个G

· · 题解

update on 2026/1/25 22:09
代码被叉了，已修复。
绷，做法本身没什么问题，但是多重背包我写挂了，这样数据都能放我过？开玩笑的吧。
原来写挂的部分放代码里了。
感谢 Re_incarnation 大神指出的错误。
对拍随了上万组，不至于再挂了吧，如果有问题欢迎继续叉。

update on 2026/1/25 23:35
被质疑正确性有误，严肃加班添加贪心正确性证明。
但是怎么题解区还有同做法正确性证明没写的，急了，那我这算啥啊？

这题做法好像很多，看到有三分套三分套二分过了的大神，那我觉得我的做法还挺正常。

看完题目之后一秒想到清仓甩卖的子问题，不同的是那个题重量最大是 2，这个题重量最大是 3，那这谁想分讨谁分讨去，反正我放弃了分讨。

思考一下按性价比直接贪为什么是错的，就是因为会选一些性价比高的小物品，然后导致最后背包空间不够选一些性价比低一点但是总价值大的大物品，只能空着或者选性价比特别低的小物品，尝试去考虑反悔贪心错掉的这部分。

清仓甩卖在最大重量为 2 的时候有且只有一种情况会错，就是最后选了个性价比高的 1 导致没法选性价比低点 2 了，需要拿 2 换出来两个。

最大重量为 3 的时候错误情况很多，谁想分讨谁分讨去。

观察到直接贪在大部分是对的，贪心方案和正确选择方案差距不会很大。

感性理解是因为你反悔拿出来几个物品之后，背包空间剩余很多的时候，可以放入大低性价比的物品空间已经被腾出来了，继续取出也找不到更优的利用法，剩下的再拿出来没意义了。

正确性严格证明如下：

考虑对比直接贪心和正确选择方案不同部分，下面提到的贪心方案和正确选择方案均指不同部分，相同部分略去不影响正确性。

正确选择方案的物品性价比一定不高于贪心得出的物品性价比，贪心性价比正确选择方案低的物品当做空置部分，这么做只会使贪心方案更劣，不影响正确性。

所以正确选择方案的物品总重大于贪心方案物品总重，不然后者性价比高，总重不低，显然更优。

同时满足贪心方案物品重量与空置部分物品重量和等于正确方案物品重量，理由显然。

一定任何不存在贪心方案的物品子集重量总和等于正确方案的物品子集重量总和，否则由于前者性价比不低于后者，前者替换后者一定不劣。

记贪心方案物品子集重量和构成的非重集为 S，正确方案物品子集和构成的非重集为 T，不然变成长难句绕口令了。

所以 S\cap T =\empty 且 \max_{u\in S}u\le \max_{v\in T}v。

因此 S 的值域连续段长度最大值小于等于 3，否则由于单个物品最大重量为 3，且 \max_{u\in S}u\le \max_{v\in T}v，则 S\cap T =\empty 一定不成立。

那么 \max_{u\in S}u\le 5，极限是 S=\{2,3,5\}，显然构造不出更优方案，也就是说贪心方案物品重量和极限是 5。

物品全部选完的情况时贪心正确，否则空置部分大小最多为 2。

那么不同部分重量即 \max_{v\in T}v 理论最大值为贪心方案物品重量加空置部分重量即 5+2=7，但是由于 \max_{u\in S}u=5 时 S=\{2,3,5\}，此时 T 无解，所以 \max_{v\in T}v 实际极限值为 6，即不同部分重量最大为 6。

证毕。

所以做法是先直接贪，然后跑两个大小为 V 的小背包，分别对应取出 i 重量的最小花费和放入 i 重量的最大收益，然后枚举不同部分重量 i，对答案取最大值。

需要注意的是原先剩余的空间是可以 0 花费用的。

我赛时没证正确性，用的 V=30，但是其实 V=6 就足够了。

代码如下。

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
struct Ty{
    int u,v,w;
    bool operator <(const Ty a)const{
        if(v*a.w!=a.v*w)return v*a.w>a.v*w;
        else return v>a.v;
    }
}x[N];
int y[N],f[35],g[35];
signed main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&x[i].w,&x[i].v,&x[i].u);
    sort(x+1,x+n+1);
    int res=0;
    for(int i=1;i<=n;i++){
        y[i]=min(x[i].u,m/x[i].w);
        res+=y[i]*x[i].v;
        m-=y[i]*x[i].w;
    }
    for(int i=0;i<=30;i++)f[i]=1e16;
    for(int i=0;i<=min(30ll,m);i++)f[i]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=min(3ll,y[i]);j++)for(int k=30;k>=x[i].w;k--)f[k]=min(f[k],f[k-x[i].w]+x[i].v);
        for(int j=1;j<=min(3ll,x[i].u-y[i]);j++)for(int k=30;k>=x[i].w;k--)g[k]=max(g[k],g[k-x[i].w]+x[i].v);
        /*原来假掉的长这样
        for(int j=1;j<=min(3ll,y[i]);j++)for(int k=30;k>=x[i].w*j;k--)f[k]=min(f[k],f[k-x[i].w*j]+j*x[i].v);
        for(int j=1;j<=min(3ll,x[i].u-y[i]);j++)for(int k=30;k>=x[i].w*j;k--)g[k]=max(g[k],g[k-x[i].w*j]+j*x[i].v);*/
    }
    int ans=0;
    for(int i=0;i<=30;i++)ans=max(ans,res-f[i]+g[i]);
    printf("%lld\n",ans);
    return 0;
}