题解：P14920 [GESP202512 六级] 道具商店

· · 题解

双倍经验。

背包变式板子，何意味。

考虑到重量很大，有 10^9，显然我们普通的 01 背包是不行的，空间时间双炸。

又发现价值很小，每件物品最多 500，总共最多 500\times n_{max} = 2.5\times 10^5。

于是考虑从价值入手，对于单个价值，贪心地肯定想要获得这个价值的重量尽可能小。

于是设 f_i 为获得价值 i 的最小重量，同 01 背包转移即可：

f_j = \min\{f_j ,f_{j - c_i} + a_i\}\left(2.5\times 10^5\ge j\ge a_i\right)

然后倒着枚举可能价值，找到第一个满足 f_i \le k 的，即可输出，价值为 i 最大（因为倒序枚举）。

时间复杂度为 \mathcal O(n^2V)，V 为 \{a_i\} 的值域。

:::success[实现]

namespace lolcrying {

    signed main(){

        n = read() ,k = read();
        up(i ,1 ,n) a[i] = read() ,c[i] = read();

        memset(f ,0x3f ,sizeof f);

        f[0] = 0 ;

        up(i ,1 ,n){
            dn(j ,250000 ,a[i]) f[j] = min(f[j] ,f[j - a[i]] + c[i]);
        }

        dn(i ,250000 ,0)
            if(f[i] <= k) {
                writeln(i) ; return 0 ;
            }

        return 0 ;
    }

}

:::