/*
The Knapsack Problem is the following: Given a collection items each
having a "size" and a "value".  Given a "knapsack" of a certina
maximum capacity, find a subset of times of maximal total value that
will fit inside the knapsack.  It can be assumed that sizes and values
are positive integers.

This problem is theoretically "NP-Complete:" this usually means that
there are only exponential-time algorithms (such as O(2**n) or O(3**n)
).  Even with dynamic programming there are situations where this
order of complexity cannot be avoided.  However, dynamic programming
can still be helpful in certain situations.  Let's jump into an example:

You are given the important task to go shopping at a wholesale market
for your family.  You have a budget of $200.  You also have a list of
items that you can consider buying, each with a number indicating its
importance.  Here, the "size" of each item is its price and the maximum
capacity of your knapsack is 200.  The "value" of an item is the
number that indicates its importance.  The value and price of an item
are not necessarily related.  The knapsack problem in this scenario is
to select a subset of items of maximal value that will fit your budget.

item                   size (rounded price)           value (importance)

bathroom tissue          $23                           100
disinfecting wipes       $13                           91
hand sanitizer           $10                           90
bottled water            $6                            95
canned fish              $28                           70
frozen vegetables        $20                           80
fresh vegetables         $15                           50
canned tomatoes          $30                           70
dried pasta              $33                           75
powdered milk            $34                           60
powdered eggs            $18                           55
instant noodles          $30                           65
sliced ham               $36                           40
fresh fruit              $20                           45
coffee                   $11                           48
soda pop                 $25                           35        
case of wine             $120                          30
potato chips             $4                            10
ice cream                $5                            2

Note that the price and value of an item do not necessarily correlate.
There could also be more than one subset that has the same maximal
value and you're only required to find one of them.

The number of subsets of a set of n items if 2**n so enumerating through 
each subset is clearly O(2**n), and is not a practical solution.  But 
in this particular problem, many subsets of items will have the same 
total size, and dynamic programming can be used to eliminate the redundant
computations that would result from a direct, recursive search.


The first stage of dynamic programming is to find a recursive solution to
the problem...
*/

import java.util.HashSet; // to represent the knapsack
import java.util.Scanner; // to read problem description from file
import java.io.*;         
public class knapsack2020 implements Runnable
{
    int[] size; // the size of each item, size[0] is size of first item
    int[] value; // the value of each item;
    int capacity;  // maximum capacity of the knapsack
    String[] description; // optional description of items, just for effect.

    public knapsack2020(int[] s, int[] v, int c, String[] d)
    {
	if (s==null || v==null || c<1 || s.length<1 || s.length!=v.length)
	    throw new RuntimeException("invalid knapsack");
	size=s;  value=v; capacity=c;
	if (d!=null && d.length==size.length) description=d;
	// number of items is size.length;
    }

// straight recursive solution: RK takes as arugments n remaining items
// and c remaining capacity, returns value of optimal subset
    public int RK(int n, int c)
    {
	if (n<1 || c<1) return 0;  // not more items or no more capacity
	int itemsize = size[n-1]; // size of nth item
	int itemval  = value[n-1]; // value of nth item
	// choose the largest of two values use, dontuse:
	int dontuse = RK(n-1,c); // value without using nth item
	int use;                 // value if nth item is used
	if (itemsize<=c) use = RK(n-1,c-itemsize) + itemval;
	else use = 0; // can't use if doesn't fit inside sack
	return Math.max(use,dontuse);
    }//recursive solution

// The recursvie solution is exponential in n+c for typical values
// of itemsize.  

//  The next step is to choose between top-down or bottom-up dynamic
// programming.  Top-down is easier to do efficiently in this case
// because not every value of RK(n,c) is required.
// For example, if all itemsize is even and capacity is also even,
// then no odd value of c is ever needed.  In general, if n is the
// row index then we have to make sure that each row contains c, c-size[n-1],
// c-size[n-2], c-size[n-3], etc... as well as c-size[n-1]-size[n-2]
// c-size[n-1]-size[n-2]-size[n-3], c-size[n-1]-size[n-3], etc for every
// possible combination of the n items.

    int[][] M; // dynamic programming matrix, must initialize to -1
    boolean[][] TB; // traceback, record choice of using or not using item
    protected int TK(int n, int c)
    {
	if (M[n][c] == -1)  // if no stored value
	    {
		int dontuse = TK(n-1,c);
		int use = 0;
		if (size[n-1]<=c) use = TK(n-1,c-size[n-1])+value[n-1];
		if (use>dontuse) { M[n][c] = use;  TB[n][c]=true; }
		else {M[n][c] = dontuse;  TB[n][c] = false; }
	    }
	return M[n][c];
    }//TK
    protected int topdown() // initialize matrix and call TK
    {
	int n = size.length;
	M = new int[n+1][capacity+1]; // need M[n][capacity] to exist
	TB = new boolean[n+1][capacity+1]; // initially all false
	for(int i=1;i<=n;i++)
	    for(int k=1;k<=capacity;k++)
		M[i][k] = -1; // -1 means invalid value
	return TK(n,capacity);
    }//topdown

    // traceback returns a set of indices of items included in knapsack
    protected HashSet<Integer> traceback()
    {
	HashSet<Integer> sack = new HashSet<Integer>(); //optimal collection
	int i = size.length, k = capacity;
	while (i>0 && k>0) // special case, don't need to go to 0,0
	    {
		if (TB[i][k]) // if ith item is used
		    {
			sack.add(i-1);  // add index of corresponding item
			k -= size[i-1];
		    }
		i--; // always decrease row number
	    }//while
	return sack;
    }//traceback

    public void run()
    {
	int totalvalue = topdown();
	HashSet<Integer> mysack = traceback();
	System.out.println("Items in your knapsack:");
	int totalsize = 0;
	for(Integer i:mysack)
	    {   String name = "item "+i;  // name of item
		if (description!=null) name=description[i];
		System.out.printf("%-20s:  size %4d,  value %5d\n",name,size[i],value[i]);
		totalsize += size[i];
	    }
	System.out.printf("Total size of %d items: %d out of capacity %d\n",mysack.size(),totalsize,capacity);
	System.out.println("Total value of items: "+ totalvalue);
    }//run


    //////////main reads info from file    
    public static void main(String[] args) throws IOException
    {
	// Test of worst-case scenario:
	// worstcase(25); System.exit(0);
	
	Scanner scin;
	String token ="";
	if (args.length==0) scin = new Scanner(System.in); // read from stdin
	else scin = new Scanner(new File(args[0]));
	if (!scin.next().equals("items")) throw new RuntimeException("invalid knapsackfile");
	int n = scin.nextInt();
	if (!scin.next().equals("capacity")) throw new RuntimeException("invalid knapsackfile");
	int cap = scin.nextInt();
	System.out.printf("reading %d items, capacity %d ...\n",n,cap);
	scin.next(); scin.nextLine(); // skip line
	int[] size = new int[n];
	int[] value = new int[n];
	String[] description = new String[n];
	for(int i=0;i<n;i++)
	    {
		description[i]="";
		token = scin.next();
		while (!token.equals(":"))
		    { description[i] += token+" "; token=scin.next(); }
		description[i] = description[i].trim();
		size[i] = scin.nextInt();
		value[i] = scin.nextInt();
		//System.out.printf("%s,  size %d, value %d\n",description[i],size[i],value[i]);	     // trace
	    }//for
	scin.close(); // closes file stream

	knapsack2020 ks = new knapsack2020(size,value,cap,description);
	ks.run();
    }//main

/*
  The exact complexity of the dynamic programming algorithm is
O(n*capacity) where n is the number of different items to choose from.
We can lazily call it O(m*m), or "polynomial time" if m = max(n,capacity).
Some call it a "pseudo polynomial time" algorithm.

Mathematically, it's not hard to concoct a scenario for which even the
dynamic programming solution is not practical.  If the total size of
each subset of items is unique, then there will be no redundant
recursive calls made by the TK function.  Let the size of first item
be any number, and the size of each successive item be one plus the
sum of the sizes of all previous numbers. For example, if items have
sizes

   1 2 4 8 16 32 64 128 ...

Because each size is a unique power of two, each subset of these
numbers will have a unique integer as its total size.  Now let
capacity be the sum of all these numbers (255 in this example), so
there's never the question of not having enough capacity.  The two
recursive calls made by TK: TK(n-1,c) and TK(n-1,c-size[n-1]) will
never be repeated, and so using a matrix to store known results will
have no effect on the program, and TK will behave in the same way as
RK.  In this example, there are 8 items and capacity is 2**8 -1 = 255.
We can can ignore the insignificant -1 and generalize the problem to n
items with a capacity of 2**n.  The size of the 2D array that we would
have to create is also exponential: n X 2**n.  The dynamic programming
solution is not any better in terms of time, plus it's now also
exponential in its use of memory.  Theoretically, therefore, the worst-case
complexity of the Knapsack problem is exponential.  

However, in the shopping list example, and in many real-life examples,
many subsets of items will have the same size and the capacity will
not be exponential in relation to the number of items (at least not
with a positive integer base).  In these situations, dynamic programming
can be used as a practical solution.
*/

// Unfortunately, a typical pc doesn't even have enough memory to
// demonstrate the hypothesis convincingly... if n=30, we will need
// 120 gigabytes of RAM (4 bytes for each int * 30 * 2**30-1).
    public static void worstcase(int n)  // don't try with n>25
    {
	int cap = (int)(Math.pow(2,n))-1;
	int[] size = new int[n];
	int[] value = new int[n];
	size[0] = 1;  value[0] = (int)(Math.random()*cap*n);
	for(int i=1;i<n;i++)
	    {
		size[i] = size[i-1]*2;
		value[i] = (int)(Math.random()*cap*n);
	    }
	knapsack2020 worst = new knapsack2020(size,value,cap,null);
	worst.run();
	System.out.println("without DP: "+worst.RK(n,cap));
    }//worstcase

/*
Lastly, some theoreticians argue that the Knapsack Problem is expoential
because you need to input a number n, followed by n pieces of information
(size and value of each item).  But a number n can be represented by 
log n bits.  The relationship between log n and n is the same as between
n and 2**n:  n = 2**(log n).  Therefore, the Knapsack problem is always
exponential in terms of n.  However, this theoretical argument doesn't have
much practical significance.   A similar argument is that calculating
2**n must be O(n) because n binary digits are required to represent 2**n
and time complexity is always lower-bounded by space (memory) complexity.
However, in practice we can still compute 2**n in log n steps by binary
factorization of n.  The theoretical argument doesn't mean that there
can't be a better algorithm.
*/    

}//knapsack2020

/*
CHALLENGE:

  Devise and implement a variant of the knapsack problem so that more
than one copy of an item can be included in the knapsack, up to some
maximum number for each item.  For example, you can buy up to 2 packs
of bathroom tissue and up to 3 bags of potato chips.  Try to implement
it by reusuing the existing code as much as possible...  Your knapsack
can no longer be represented by a *set* because there could be multiple
instances of the same item in the sack.  ... But maybe you can still
manage it somehow ... You've got to "think outside of the sack."
*/