DP - Knapsack Summary
https://blue2048.iteye.com/blog/2152688
Given a knapsack with capacity W:
Pack as many items into the knapsack such that the total value of the items packed is maximized
Recursive Version:
Running time = O(WN)
Multiple Restriction Knapsack
http://rosettacode.org/wiki/Knapsack_problem/Unbounded#Java
https://blue2048.iteye.com/blog/2152688
在01背包中，v变化的区间是逆序循环的原因：要保证由状态f[i-1][v-c[i]]递推状态f[i][v]时，f[i-1][v-c[i]]没有放入第i件物品。之后，在第i循环时，放入一件第i件物品。
- f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + Value[i])
在完全背包中，v变化的区间是顺序循环的原因：完全背包的特点是每种物品可选无限件，在求解加选第i种物品带来的收益f[i][v]时，在状态f[i][v-c[i]]中已经尽可能多的放入物品i了，此时在f[i][v-c[i]]的基础上，我们可以再次放入一件物品i，此时也是在不超过背包容量的基础下，尽可能多的放入物品i。
完全背包的方程：
- f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);
举例：
物品个数N = 3，背包总容量为V = 5。
物品信息：
完全背包：
分析：
i = 2，表示正在处理第2件物品。在求解f[2][4]时，如果要计算把第2件物品放入背包后的代价时，我们需要知道f[2][2],此时f[2][2]中已经尽全力放入第2件物品了（已经放入一件）。此时此刻还可以在放入一件第2件物品，在背包容量为4时，最多可以放入两件第二件物品。
总结下，f[i][v]:表示在背包容量为v时，尽全力的放入第i件物品的代价。f[i][v - weight[i]]:表示在背包容量为v - weight[i]时，尽全力的放入第i件物品的代价。因此由f[i][v - weight[i]]转换为f[i][v]时，也是在f[i][v - weight[i]]的基础上有加入了一件物品i。
为了节省保存状态的空间，可以直接使用一维数组保存状态。
代码：迭代方程：f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/knapsack2.htmlGiven a knapsack with capacity W:
Pack as many items into the knapsack such that the total value of the items packed is maximized
Recursive Version:
/* ========================================================
M(C) = max value achieved by knapsack with capacity C
======================================================== */
static int M(int[] v, int[] w, int C)
{
int[] sol, mySol;
int i, myFinalSol;
sol = new int[v.length];
mySol = new int[v.length];
/* ---------------------------
Base cases
--------------------------- */
if ( C == 0 )
{
return(0);
}
/* ==============================================
Divide and conquer procedure
============================================== */
/* ---------------------------------------
Solve the appropriate smaller problems
--------------------------------------- */
for ( i = 0; i < v.length; i++ )
{
if ( C >= w[i] )
sol[i] = M( v, w, C-w[i] ); // Knapsack capacity reduced by w[i]
// because it has item i packed in
// it already
else
sol[i] = 0; // Not enough space to pack item i
}
/* ---------------------------------------------
Use the solutions to the smaller problems
to solve original problem
--------------------------------------------- */
for ( i = 0; i < v.length; i++ )
{
if ( C >= w[i] )
mySol[i] = sol[i] + v[i]; // Value is increased by v[i]
// because it has item i packed in
// it already
else
mySol[i] = 0; // Not enough space to pack item i
}
/* *************************
Find the best (maximum)
************************* */
myFinalSol = mySol[0];
for ( i = 1; i < v.length; i++ )
if ( mySol[i] > myFinalSol )
myFinalSol = mySol[i];
return myFinalSol; // Return the overal best solution
}
Bottom-up Dynamic Programming solution for Unbounded KnapsackRunning time = O(WN)
/* ========================================================
M_dp(W) = max value achieved by knapsack with capacity W
======================================================== */
static int M_dp(int[] v, int[] w, int W)
{
int[] sol, mySol;
int i, myFinalSol;
int[] M; // Data structure to store results
int C; // Index to run through M[]
sol = new int[v.length];
mySol = new int[v.length];
M = new int[W + 1]; // Create array
/* ---------------------------
Base cases
--------------------------- */
M[0] = 0;
/* ==============================================
The other values M[C]
============================================== */
for ( C = 1; C <= W; C++ )
{
/* ---------------------------------------
Solve the appropriate smaller problems
--------------------------------------- */
for ( i = 0; i < v.length; i++ )
{
if ( C >= w[i] )
sol[i] = M[ C-w[i] ]; // Knapsack capacity reduced by w[i]
// because it has item i packed in
// it already
else
sol[i] = 0; // Not enough space to pack item i
}
/* ---------------------------------------------
Use the solutions to the smaller problems
to solve original problem
--------------------------------------------- */
for ( i = 0; i < v.length; i++ )
{
if ( C >= w[i] )
mySol[i] = sol[i] + v[i]; // Value is increased by v[i]
// because it has item i packed in
// it already
else
mySol[i] = 0; // Not enough space to pack item i
}
/* *************************
Find the best (maximum)
************************* */
M[C] = mySol[0];
for ( i = 1; i < v.length; i++ )
if ( mySol[i] > M[C] )
M[C] = mySol[i];
}
return M[ W ]; // Return best value for knapsack of cap = W
}
http://times.imkrisna.com/2010/05/unbounded-knapsack-java-source-code/Multiple Restriction Knapsack
http://rosettacode.org/wiki/Knapsack_problem/Unbounded#Java
public UnboundedKnapsack() { // initializing: for (int i = 0; i < n; i++) { maxIt [i] = Math.min( (int)(sack.getWeight() / items[i].getWeight()), (int)(sack.getVolume() / items[i].getVolume()) ); } // for (i) // calc the solution: calcWithRecursion(0); // Print out the solution: NumberFormat nf = NumberFormat.getInstance(); System.out.println("Maximum value achievable is: " + best.getValue()); System.out.print("This is achieved by carrying (one solution): "); for (int i = 0; i < n; i++) { System.out.print(bestAm[i] + " " + items[i].getName() + ", "); } System.out.println(); System.out.println("The weight to carry is: " + nf.format(best.getWeight()) + " and the volume used is: " + nf.format(best.getVolume()) ); } // calculation the solution with recursion method // item : the number of item in the "items" array public void calcWithRecursion(int item) { for (int i = 0; i <= maxIt[item]; i++) { iIt[item] = i; if (item < n-1) { calcWithRecursion(item+1); } else { int currVal = 0; // current value double currWei = 0.0; // current weight double currVol = 0.0; // current Volume for (int j = 0; j < n; j++) { currVal += iIt[j] * items[j].getValue(); currWei += iIt[j] * items[j].getWeight(); currVol += iIt[j] * items[j].getVolume(); } if (currVal > best.getValue() && currWei <= sack.getWeight() && currVol <= sack.getVolume() ) { best.setValue (currVal); best.setWeight(currWei); best.setVolume(currVol); for (int j = 0; j < n; j++) bestAm[j] = iIt[j]; } // if (...) } // else } // for (i) } // calcWithRecursion()
