背包九讲代码
1、01背包。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
2、完全背包
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
3、多重背包
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
可以转换为01背包，可以把n件可用的物品等效为n个相同值，放到数组里。
用到快速幂方法，把这个O(n)复杂度降低为O(logn)