p3462 sol（POI2007 ODW）

AllenJYL · 2024-12-18 21:37:47 · 题解

考虑类 k 进制下的情况。将每个背包改写成物品重量（或 1）与一个系数之积的和。考虑从小到大填充物品。

比如说，物品重量为 3,6,9,18，背包重量为 29 时，背包重量可以改写为 18\times1+9\times1+6\times0+3\times0+1\times2。我们把每一项称作一位，每一项的系数看作对应位上的数位值，那么 29 就可以被描述为一个五位数。

对于当前物品的重量，尝试找到它对应位上数位值大于 0 的一个背包，将物品贪心放入，并将对应位的数位值减去 1。如果无法找到，那么尝试 “退位”，类似于减法意义下的退位。比如说 9 可以退位为一个 6 和一个 3。优先找物品重量小的位尝试退位即可。