import orbital.math.MathUtilities;
/**
* Knapsack problem solved with dynamic programming.
* Knapsack is NP-complete.
*
* @author Uwe Aßmann
* @author André Platzer
* @version $Id: KnapsackDP.java 1728 2006-08-30 18:06:46Z andre $
* @TODO: implements DynamicProgrammingProblem
*/
public class KnapsackDP {
public static void main(String arg[]) {
new KnapsackDP(6, new int[] {
1, 2, 2, 3, 4, 5
}).solve();
}
private static final int NOSOLUTION = 0;
private static final int SOL_TAKE = 1;
private static final int SOL_LEAVE = 9;
private int[] element;
private int size;
/*
*
* - dp[i, j], where i = #Elements, j = 0..size of knapsack
*
- dp[i, j, 0] == NOSOLUTION <=> there is no solution
*
- dp[i, j, 0] == 1 <=> there is a solution
*
- dp[i, j, 1] == SOL_LEAVE <=> there is a solution without element i
*
- dp[i, j, 1] == SOL_TAKE <=> there is a solution with element i
*
*/
private double dp[][];
public KnapsackDP(int size, int[] element) {
this.size = size;
this.element = element;
dp = new double[element.length][size];
}
public void solve() {
solveByDynamicProgramming();
System.out.println(MathUtilities.format((double[][]) dp));
}
/**
* Method declaration
*
* O(n*K)
* @see
*/
private void solveByDynamicProgramming() {
for (int i = 0; i < size; i++) { // initialize
dp[0][i] = NOSOLUTION;
}
dp[0][0] = SOL_LEAVE;
for (int i = /* 0 */ 1; i < element.length; i++) {
for (int k = 0; k < size; k++) {
dp[i][k] = NOSOLUTION; // initialize
if (dp[i - 1][k] != NOSOLUTION) {
dp[i][k] = SOL_LEAVE;
} else {
if (k - element[i] >= 0) {
if (dp[i - 1][k - element[i]] != NOSOLUTION) {
dp[i][k] = SOL_TAKE;
}
}
}
}
}
}
}