/*
   The Knapsack Problem is an interesting topic in computer science
because, theoretically, the problem is "NP-complete," which usually
means that there can be no practical solution to the problem that's
reasonably efficient.  While that's true in a theoretical sense, and
in the worst possible scenario, in practice the Knapsack Problem can
usually be solved effectively using dynamic programming.

The problem is as follows:

You have:

1. A "knapsack" with a maximum size or capacity.  Call this value MAX.
2. A set of n items; each item is of a certain size.
3. Each item also has a "value". The value and size of items are not
   necessarily the same.

The problem is to fill the knapsack with a collection of items that will
have maximum value.  In otherwords, find a subset of the n items that will
have the highest possible total value and will still fit inside the knapsack.

For example, let's say you've been given a shopping list and a budget
of $100 to go to the supermarket.  Each item in the market has a
price.  Here, MAX=100 and n is the total number of items on your
shopping list. The price is the "size" of each item.  The list is also
prioritized, so the most important items on your list will have the
highest value (the price and the value are not necessarily
proportional).  You need to buy a selection of items that will have
the highest possible value AND with a total price that fits your budget.

To make the problem suitable for dynamic programming, n cannot be too
large, and MAX should be approximately "linearly proportional" to n.
(for example, MAX=4n).  Of course, any two constants are linearly
proportional to eachother, so this statement is intended as an
informal approximation.  For example, if n=100, MAX should not be
10000, which is n*n.

Finally, we should round off the prices of items into integer values.
*/

import java.util.Set;
import java.util.TreeSet;

class knapsack
{
    protected int Max;  // size or capacity of knapsack.
    protected int N;    // total number of items to choose from
    protected int[] Size; // size of each item, size[0] is size of first item..
    protected int[] Value; // value of each item
    protected String[] Description; // string description of each item

    public knapsack(int c, int n, int[] S, int[] V, String[] D)
    {
	if (c<1 || n<1 || S==null || V==null || D==null
	    || S.length!=n || V.length!=n || D.length!=n)
	    throw new RuntimeException("invalid knapsack");
	Max = c;  N = n; Size=S;  Value=V; Description=D;
    }// constructor

    // Recursive solution that takes exponential time: function will
    // return the total value of the optimal selection.  Here, n is
    // the number of items left to choose from (initially N) and c is the
    // remaining capacity of the knapsack (initially MAX)
    protected int ksack(int n, int c)
    {
	if (n<1) return 0; // base case
	// consider the nth item, which has size Size[n-1], Value[n-1]:
	// we either keep the nth item in the knapsack, or don't keep it,
	// so we recursively calculate the maximum values resulting from each
	// choice, and return the larger of the two values:
	
	int dontkeep = ksack(n-1,c); // capacity same since nth item not used
	int keep = 0; // now calculate the value of keeping the nth item
	if (Size[n-1]<=c) // does this item even fit in the knapsack?
	    keep = ksack(n-1,c-Size[n-1]) + Value[n-1];  // keep it!
	return Math.max(keep,dontkeep);
    }// non-optimized function

    // Since there are 2 choices for each item, the number of possibile
    // solutions is therefore 2**n, and that's also the complexity of this
    // algorithm.
   
    // For this problem, it's better to use top-down dynamic programming
    // because of 'c-Size[n-1]'. So for example, if the sizes of all items
    // are odd values, then half the matrix won't need to be calculated.

    // Notice that we cannot assume that a value of 0 in the matrix indicates
    // that there's no solution stored there, becase 0 may indeed be the
    // correct answer: for example, what if every item in the store costs more
    // than $100?  Your solution will just be the empty set, which has value 0.
    // When initializing the matrix, we'll need to set each value to -1.

    // This problem also requires a traceback stage: we need another matrix
    // to track whether an item was "kept" or not at each step.

    protected int[][] KM; // the dynamic programming matrix
    protected boolean[][] Kept; // array for traceback
    protected void init()
    {
	KM = new int[N+1][Max+1];  // initially all zeros
	for(int i=1;i<N+1;i++)
	    for(int k=0;k<Max+1;k++)
		KM[i][k] = -1;
	Kept = new boolean[N+1][Max+1]; // initially all false
    }
    protected int Dsack(int n, int c) // top-down dynamic programming
    {
	if (KM[n][c]<0) // no solution present
	    {
		//if (n<1) K[n][c] = 0;  // can be done by init
		int dontkeep = Dsack(n-1,c);
		int keep = 0; 
		if (Size[n-1]<=c)
		    keep = Dsack(n-1,c-Size[n-1]) + Value[n-1];
		if (keep>=dontkeep)
		    {
			KM[n][c] = keep;
			Kept[n][c] = true;
		    }
		else
		    {
			KM[n][c] = dontkeep;
		        Kept[n][c] =false;  // K[n][c] may change
		    }
	    }// if no solution present
	return KM[n][c];
    }//Dsack

    protected Set<Integer> Sack; // the solution
    public Set<Integer> getSack() { return Sack; }
    public int solve() // public interface function, returns optimal value
    {
	init();
	int totalvalue = Dsack(N,Max);
	Sack = new TreeSet<Integer>(); // red-black tree implemention of set
	// TRACEBACK stage:
	int i = N, k = Max;
	while (i>0)
	    {
		if (Kept[i][k]) { Sack.add(i);  k -= Size[i-1]; }
		i--;
	    }
	return totalvalue;
    }// solve

    public String report() // called after solve
    {
	if (Sack==null) return "report not ready";
	int val = 0;  // may need to recalculate (not hard anyway)
	int size = 0; // total size/worth of selection
	String r = "One optimal selection consists of: ";
	for(Integer i:Sack)
	    {
		r += Description[i-1] + ":"+Value[i-1]+ ","+Size[i-1]+"; ";
		val += Value[i-1];
		size += Size[i-1];
	    }
        r = r.substring(0,r.length()-2); // get rid of last "; "
	r += "\nValue of selection = " +val;
	r += "\nWorth of selection = " + size;
	return r;
    }//report
}//knapsack class

// test case
public class knapsack17
{
    public static void main(String[] av)
    {
	int budget = 20; // only $20 to spend!
	if (av.length>0) budget = Integer.parseInt(av[0]);
	int n = 10;
	String[] description = {"carrots","coffee","ham","salmon","tomatoes","bananas","pepperoni","ground chicken","diet soda","eggs"};
	// prices in whole dollars:
	int[] price={1,8,10,15,3,4,5,7,5,3};
	int[] priority={3,2,8,4,5,6,7,9,1,10}; // eggs have top priority

	knapsack KS = new knapsack(budget,n,price,priority,description);
	KS.solve();
	System.out.println(KS.report());
    }//main
}

/*
    The analysis of the time complexity of this algorithm is a tricky
subject and can easily be misunderstood.  The size of the matrix (KM)
is on the order of N*Max.  If we can assume that MAX = KN for some
constant K, then clearly the size of the matrix is O(N*N).

However, in theoretical computer science we need to note that it takes
log(n) bits to represent a number n.  But n is exponential in terms of
log(n): n == 2**(log n).  This observation is relevant to the knapsack
problem because the *input* to the problem is not just two numbers,
but n *items*, each item has at least a size.  Ignoring the value and
"description" for the moment, and assuming that each size is bound by
MAX, then each piece of information requires at least log(MAX) bits to
represent, and there are n pieces of information, therefore the input
to the problem is on the order of N*log(MAX).  Since Max = 2**(log MAX),
the size of our matrix, and therefore the time complexity of our
algorithm, is on the order of N * 2**(log MAX), which is not polynomial
in terms of the size of the input.

But in practice, the size of each piece of information is bounded by a
constant, in the case of this specific program, each "size" is exactly
a 32 bit int.  Thus the size of our input is 32N, which is O(N), so we
can still say that this *implementation* of the algorithm is O(N*N).  

What is important in practice is that MAX cannot be too large relative
to N. You could have the following worst-case scenario:

  Let p(i) be some permutation (one-one function) on numbers from 1 to N,
  Let Size[i] = 2**p(i).  

Here, each subset of items will have a *unique* size that corresponds to
a binary number.  Since there are 2**n subsets of the N items, there is
no way to find the optimal subset without enumerating through every subset.
Even with dynamic programming, here MAX is exponentional in terms of N,
and our algorithm will have the real-time behavior of an exponential-time
algorithm.  Also, in practice we need to be concerned with creating matrices
that are too large, and with stack overflow that can be caused by too much 
recursion (here, the depth of recurision is bound by MAX).  
*/