/* Knapsack Problem and Dynamic Programming 
   // three versions:
   1. with no optimization
   2. with memoization or top-down dynamic programming
   3. with bottom-up dynamic programming.
   Recommended solution is top-down dynamic programming for this example.
*/

import java.util.TreeSet;

public class knapsack
{
    int capacity; // total size of knapsack
    int[] size; // size of each item;
    int[] value; // value of each item
    // number of items is size.length;

    public knapsack(int c, int[] s, int[] v)
    {
	if (c<0 || s==null || v==null || s.length!=v.length) 
	    throw new RuntimeException("invalid knapsack");
	capacity = c;
	size = s;  
	value = v;
    }//constructor

    // Non-optimized recursive solution:
    // K computes max value based on n remaining items and S remaining
    // space.  initially called with K(s.size,capacity).
    // First item is 0th item.  The value returned is the optimal value
    // (not space) of a collection of up to n items with S remaining space.
    public int K(int n, int S)
    {
	if (n<1) return 0;
	int dontuse = K(n-1,S);
	int use = 0; // computed below
	if (size[n-1] < S)
	    {
		use = value[n-1] + K(n-1,S-size[n-1]);
	    }
	if (use>dontuse) return use; else return dontuse;
    }
    // complexity is O(2**n): T(n) = 2T(n-1) + 1 best describes K

    // top-down dynamic programming solution
    protected int[][] M; // matrix of values;
    protected boolean[][] solution;  //solution[i][S] iff i part of solution
    public TreeSet<Integer> sack; // the solution
    public int Ktd()
    {
	int n = size.length;
	int S = capacity;
	M = new int[n+1][S+1]; // initially all zeros
	solution = new boolean[n+1][S+1];
	sack = new TreeSet<Integer>(); // empty sack
	for(int i=0;i<(n+1)*(S+1);i++)
	    M[i/(S+1)][i%(S+1)] = -1;  // use -1 to mean no value;
	// note, M[i][j]!=-1 does not mean solution[i][j]==true
	int answer = K2(n,S);
	// reconstruct solution:
	int i = n;
	while (i>0)
	    {
		if (solution[i][S])
		    {
			sack.add(i-1);
			S = S-size[i-1];
		    }
		i--;
	    }
	return answer;
    }
    protected int K2(int n, int S) // helper function
    {
	if (n<1) return 0;
	if (M[n][S] == -1) 
	    {
		int dontuse = K2(n-1,S);
		int use = 0; // computed below
		if (size[n-1] < S)
		    {
			use = value[n-1] + K2(n-1,S-size[n-1]);
		    }
		if (use>dontuse) 
		    {
			M[n][S] = use;
			solution[n][S] = true;
		    }
		else M[n][S] = dontuse;
	    }
	return M[n][S];
    }//K2 and Ktd

    // Complexity: O(n*n): "dynamic" because static recurrence
    // T(n) = 2T(n-1)+1 no longer applies.

    // bottom-up solution
    public int Kbu()
    {
	int n = size.length;
	int S = capacity;
	// this time, second coord of M (j) represents S-size[j-1]
	M = new int[n+1][S+1]; // initially all zeros
	solution = new boolean[n+1][S+1];  // initially all false;
	sack = new TreeSet<Integer>(); // empty sack
	for(int i=1;i<=n;i++) // i represents each of n items
	  {
	    for(int j=0;j<=S;j++) // j represensts possible values of S (size)
	    {
		int dontuse = M[i-1][j]; 
		int use = 0;
		if (size[i-1] < j)
		   use = value[i-1] + M[i-1][j-size[i-1]];
		if (use>dontuse)
		    {
			M[i][j] = use;
			solution[i][j] = true;
		    }
		else M[i][j] = dontuse;
	    }//for j (size)
	  }// for i  (item number)

	// reconstruct solution:
	int i = n;
	while (i>0)
	    {
		if (solution[i][S])
		    {
			sack.add(i-1);
			S = S-size[i-1];
		    }
		i--;
	    }
	return M[n][S];
    }//Kbu

    public static void main(String[] av)
    {
	//	int[] size = {9,8,6,5,4,4,3,2};
	int[] size = {90,80,60,50,40,40,33,122};
	int[] value = {9,8,6,5,4,4,3,2};
	int capacity = 20; //30;
	if (av.length>0) capacity = Integer.parseInt(av[0]);
	knapsack KS = new knapsack(capacity,size,value);
	System.out.println("non-optimized :" + KS.K(size.length,capacity));
	System.out.println("top-down: "+KS.Ktd());
	for(Integer i : KS.sack) System.out.print(i+ ":"+size[i]+","+value[i]+" ");
	System.out.println("\nbottom-up: "+KS.Kbu());
	for(Integer i : KS.sack) System.out.print(i+ ":"+size[i]+","+value[i]+" ");
    }
}//knapsack

/*
 In Theoretical computer science the Knapsack problem is
"NP-Complete".  This means that there is no known polynomial-time
algorithm that can solve the problem and likely won't ever be (unless
"P=NP").  This would appear to contradict our dynamic programming
solutions above, which appear to run in n-squared time, which is
certainly polynomial (actually time n*S, but we can assume that S and
n are different by a constant factor, for example, S<4n).  This
discrepancy is due to two facts:

1. Given a set of n items, there are 2**n different subsets, so to
enumerate every subset and examine it would clearly take O(2**n) time.
But notice that our programs do not compute EVERY optimal solution but
just ONE optimal solution.  For example, say the size (capacity) of
the knapsack is 3 and there are 9 items to choose from, each with size
and value 1.  Then there are a total of 9!/(6!*3!) = 84 equally
optimal solutions (choose any 3 items out of the nine).  But we are
not enumerating through all of them: our programs just pick one.

2. In our programs the size of the input is constant: both n and S are
of type "int", which means they're fixed, 32-bit values.  However,
mathematically speaking the capacity can be arbitrarily large, which
means it takes log(size) bits to represent.  Assume that size and n
are approximately the same.  The relation between log(n) and n*n is
2**(2*log(n)), and so the solution is, in this strictly mathematical
sense, exponential in terms of the size of the input.  Practically
speaking, however, this is usually not a concern since we usually fix
the size of the input to a constant such as 32 or 64 bits.

This descrepancy occurs quite often in computer science.  For example,
theoretically, calculating 2**n cannot be done in less than O(n) time
because it takes n bits to represent 2**n.  Time complexity is always
greater than or equal to space (memory) complexity because it take at
least that much time to fill the space.  However, if we fix the size
of 2**n to be, say 64 bits, then 2**n can be calculated in log(n)
steps using binary factorization of n (2**n = (2**n/2)**2).
*/