p3462 sol（POI2007 ODW）

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

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

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