状压 dp.
考虑将所有包按照容量从大到小排序,从前往后依次装好每个包.
设 $f(S)$ 表示已经装了集合 $S$ 中的物品,最少用的包的数目,.
设 $g(S)$ 表示在用最少的包的前提下,最后的那个包最多还剩的容量.
枚举加入哪个物品,若剩余容量足够,就加入剩余容量,否则去新开一个包.
1 | //%std |
夢はここに 思い出は遠くに
状压 dp.
考虑将所有包按照容量从大到小排序,从前往后依次装好每个包.
设 $f(S)$ 表示已经装了集合 $S$ 中的物品,最少用的包的数目,.
设 $g(S)$ 表示在用最少的包的前提下,最后的那个包最多还剩的容量.
枚举加入哪个物品,若剩余容量足够,就加入剩余容量,否则去新开一个包.
1 | //%std |