讲透完全背包算法 - Unbounded knapsack problem
s[i][j]=max{s[i-1][j], s[i][j-v[i]]+w[i]}
for (int i=1; i<=N; i++)
{
for (int j=v[i]; j<=V; j++) s[j]=max(s[j], s[j-v[i]]+w[i]);
}
https://github.com/PetarV-/Algorithms/blob/master/Dynamic%20Programming/Unbounded%20Knapsack.cpp
0/1背包和完全背包的java解法
若两件物品i、j满足c[i]<=c[j]且w[i]> =w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。
把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足c[i]*2^k<=V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品
http://www.ahathinking.com/archives/108.html
http://sighingnow.github.io/algorithm/coin.html
仅有 n 种指定面值的硬币(c1, c2, c3, ..., cn), 将钱 N 兑换成 这些面值的硬币，总共有多少种兑换方法？
Read full article from 讲透完全背包算法 - Unbounded knapsack problem
已知:有一个容量为V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。
条件:每种物品都有无限件，能放多少就放多少。
问题:在不超过背包容量的情况下，最多能获得多少价值或收益
http://ufownl.blog.163.com/blog/static/1250122200933113914579
基于01背包的分析，由于不必考虑物品的重复放入，故v的循环采用顺序即可。代码如下：
for(i = 0; i < N; ++i) { for(j = weight[i]; j <= V; ++j) /* j<weight[i]的对前面的状态不会有影响 */ { int tmp = maxV[j-weight[i]]+value[i]; maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp; } }s[i][j]=max{s[i-1][j], s[i][j-v[i]]+w[i]}
for (int i=0; i<=V; i++) s[0][i]=0; // 边界
for (int i=1; i<=N; i++)
{
for (int j=0; j<=V; j++)
{
int t=0;
for (int i=1; i<=N; i++)
{
for (int j=0; j<=V; j++)
{
int t=0;
if (j-v[i]>=0) t=s[i][j-v[i]]+w[i];
s[i][j]=max(s[i-1][j], t);
}
}
将状态记录数组改成一维可以将空间复杂度降为O(V)s[i][j]=max(s[i-1][j], t);
}
}
for (int i=1; i<=N; i++)
{
for (int j=v[i]; j<=V; j++) s[j]=max(s[j], s[j-v[i]]+w[i]);
}
https://github.com/PetarV-/Algorithms/blob/master/Dynamic%20Programming/Unbounded%20Knapsack.cpp
0/1背包和完全背包的java解法
public static int unpack(int[] values, int[] weights, int maxWeight) {
int[] ans = new int[maxWeight + 1];
for (int i = 0; i < values.length; i++) {
for (int j = weights[i]; j <= maxWeight; j++) {
int takeValue = values[i] + ans[j - weights[i]];
if (takeValue > ans[j]) {
ans[j] = takeValue;
}
}
}
return ans[maxWeight];
}
基本思路（直接扩展01背包的方程）
由于本问题类似于01背包问题，在01背包问题中，物品要么取，要么不取，而在完全背包中，物品可以取0件、取1件、取2件...直到背包放不下位置。因此，可以直接在01背包的递推式中扩展得到。
- f[i][v]:表示前i件物品放入容量为v的容量中时的最大收益
- 递推式：
- f[i][v] = max(f[i - 1][v],f[i - K * weight[i]] + K * Value[i]); 其中 1 <= K * weight[i] <= v,(v指此时背包容量)
程序需要求解N*V个状态，每一个状态需要的时间为O（v/Weight[i]），总的复杂度为O(NV*Σ(V/c[i]))。
- int Completeknapsack()
- {
- //边界条件
- for (int i = 0;i <= N;i++)
- {
- f[i][0] = 0;
- }
- for (int v = 0;v <= V;v++)
- {
- f[0][v] = 0;
- }
- //递推
- for (int i = 1;i <= N;i++)
- {
- for (int v = 1;v <= V;v++)
- {
- f[i][v] = 0;
- int nCount = v / weight[i];
- for (int k = 0;k <= nCount;k++)
- {
- f[i][v] = max(f[i][v],f[i - 1][v - k * weight[i]] + k * Value[i]);
- }
- }
- }
- return f[N][V];
- }
3、转换为01背包问题求解（直接利用01背包）
思路 1、完全背包的物品可以取无限件，根据背包的总容量V和第i件物品的总重量Weight[i],可知，背包中最多装入V/Weight[i](向下取整)件该物品。因此可以直接改变第i件物品的总个数，使之达到V/Weight[i](向下取整)件，之后直接利用01背包的思路进行操作即可。
举例：物品个数N = 3，背包容量为V = 5。
拆分之前的物品序列：
拆分之后的物品序列：
若两件物品i、j满足c[i]<=c[j]且w[i]> =w[j]，则将物品j去掉，不用考虑。这个优化的正确性显然：任何情况下都可将价值小费用高得j换成物美价廉的i，得到至少不会更差的方案。
把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足c[i]*2^k<=V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品
http://www.ahathinking.com/archives/108.html
这种实现方式是对完全背包的基本实现做了一个优化，叫“二进制拆分”。所谓“拆分物体”就是将一种无限件物品拆分成有效的几件物品，拆分物体的目的是通过减少物品个数来降低复杂度。
在完全背包中，每种物品i对于容量v来讲实际上相当于有v/c[i]件，故在上述的基本实现中，k就要循环测试v/c[i]次。
这里的拆分是利用了一种二进制思想：即任何数字都可以表示成若干个2^k数字的和，例如7可以用1+2+2^2表示；这很好理解，因为任何正数都可以转成二进制，二进制就是若干个“1”（2的幂数）之和。
所以不管最优策略选择几件物品i，我们都可以将物品i拆成费用为c[i]*2^k，价值为w[i]*2^k的若干件物品。这样物品的状态数就降为了log(v/c[i])，是很大的改进。
* 状态转移方程：f(i,v) = max{ f(i-1,v-2^k*c[i]) + 2^k*w[i] | 0<=k<=log v/c[i] } * 每件物品降低为 log(v/c[i]) 种状态 */for(k = 1; k <= j/weight[i]; k <<= 1){ if(maxV[i-1][j-k*weight[i]] + k*value[i] > max_tmp) { max_tmp = maxV[i-1][j-k*weight[i]] + k*value[i]; }}
完全背包中的逆向思维
我们知道，在01背包和完全背包的实现中，都是针对每种物品进行讨论，即外循环都是for i=0…n，然后每种物品对于容量v的变化而求得最大价值；
在完全背包中，由于物品的件数无限，所以我们可以倒过来想，我们针对每个容量讨论，外循环为容量，对于每个容量j，我们求j对于所有物品能装载的最大价值，这样一来我们就能将时间复杂度降为O(N*V)了。
for(i = 1; i <= V; ++i) { int i_maxV = 0; /* 记录子问题i的最优解 */ /* 每个容量求面对所有物体能装载的最大价值 */ for(j = 0; j < N; ++j) { if(i >= weight[j]) { int tmp = maxV[i-weight[j]] + value[j]; maxValue[i][j] = maxV[i-1] > tmp ? maxV[i-1] : tmp; }else { maxValue[i][j] = maxV[i-1]; } if(maxValue[i][j] > i_maxV) { i_maxV = maxValue[i][j]; } } maxV[i] = i_maxV; }仅有 n 种指定面值的硬币(c1, c2, c3, ..., cn), 将钱 N 兑换成 这些面值的硬币，总共有多少种兑换方法？
最简单的递推的想法: 枚举每种货币的使用次数，当使用
k 次第 n 种硬币凑出了 j 钱数的方案，应当等于只使用了前 n-1 种硬币凑出了 dp[j-k*coin[n]] 钱数，而凑出钱数 money 的总方案，应当等于仅使用了 前 1 中硬币、仅使用的前 2 种硬币、...、仅使用了前 n-1 中硬币、使用了全部n种硬币的方案的总和。暗按照这个想法，直接递推求解即可。int dp[MAX_N] = {0};
int exchange(int money, int n, int coin[]) {
dp[0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = money; j >= coin[i]; --j) {
for(int k = j / coin[i]; k > 0; --k) {
dp[j] += dp[j - k*coin[i]];
}
}
}
return dp[money];
}
这个方法还可以进一步简化。在上面的方法中，我们从大往小地枚举钱数，考虑到每种硬币都有无限枚可以选，因此，在选择第 i 中硬币时，我们只需要从一个绝无已经选择第
i 种硬币的可能的情形 开始枚举递推即可。在具体实现上，只要改变总钱数 j 的递推顺序即可。进一步地，采用压缩空间的写法，代码如下：int dp[MAX_N] = {0};
int exchange(int money, int n, int coin[])
{
dp[0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = coin[i]; j <= money; ++j) {
dp[j] += dp[j-coin[i]];
}
}
return dp[money];
}
这种方法与求解完全背包的算法的思路有很大的相似之处。
母函数
钱币兑换问题本质上是一个组合问题：以 n 中硬币来组合出制定的钱数。因此，也可以通过母函数的方法来求解钱币组合问题。
f(n) = (1+x+x^(c1)+x^(2*c1)+...) * (1+x+x^(c2)+x^(2*c2)+...) * (1+x+x^(c3)+x^(2*c2)+...) * ... * (1+x+x^(cn)+x^(2*cm)+...)
所要求的兑换方案数，即第 n 项的系数，接下来，模拟多项式展开即可。
https://mytwocentsads.wordpress.com/2012/09/01/knapsack-problem-a-java-implementation/Read full article from 讲透完全背包算法 - Unbounded knapsack problem
