求解《双肩包九讲》中的多重背包
求解《背包九讲》中的多重背包各位大犇好！小弟看了《背包九讲》中的多重背包。理解了前面的 〇（V∑n[i]） 的暴力算
求解《背包九讲》中的多重背包
各位大犇好！
小弟看了《背包九讲》中的多重背包。理解了前面的 〇（V∑n[i]） 的暴力算法。
但对于后面的把每件物品拆分成若干件个系数的和表示 这种方法不是很理解。
暴力方法 对于 n[i]件物品，每件都考虑了。
但系数方法，只是对 1,2,4，……n[i] - 2 ^ k + 1 中方法进行了考虑。会不会有遗漏或考虑不周啊？
算法?，DP，背包，背包九讲
[解决办法]
不会， 1,2,4，……n[i] - 2 ^ k + 1能组成从1到n[i]的所有数
[解决办法]假设A代表选2件，B代表选4件，如果状态转移的时候AB都选那就等于选了6件。
[解决办法]那个暴力方法就是一个一个的取
二进制分解方法就是你可以一次去1个，或者2个，或者4个，...，或者2^k个，或者n[i]-2^k+1个
比如说暴力方法你取了3次，就是1+1+1；
而二进制分解法只需要两次就可以第一次取1个，第二次取2个：1+2
