// Knapsack solver, by Amir Kamil
import java.io.*;
import java.util.*;
 
public class Knap {
    static final int DEFAULT_N_BOOKS = 5000;
    static final int DEFAULT_BAG_CAP = 1000;
    static final int DEFAULT_max_random_weight = 2000;
    static final int DEFAULT_max_random_profit = 50;
    
    static int n_books = DEFAULT_N_BOOKS;
    static int bag_cap = DEFAULT_BAG_CAP;
    static int[1d] local weight;
    static int[1d] local profit;
    static int[2d] local total;
    static int[2d] local total_total;
    static boolean[1d] local use_book;
    
    static int cap_per_block;
    static int books_per_proc;
    static int n_blocks;
    
#define DEBUGMACRO 1
#ifdef DEBUGMACRO
//#define debug(s, level) do { String _s = s; if (DEBUG_LEVEL >= level) System.out.println(_s); } while(false)
#define debug(s, level) if (DEBUG_LEVEL >= level) System.out.println(s)
#else
    static inline void debug(String s, int level) {
	if (DEBUG_LEVEL >= level)
	    System.out.println(s);
    }
#endif

    public static void main (String[] args) {
	int total_profit, total_weight, book_i, n_sold;
	Timer solve_timer, backtrack_timer;
	int[1d] single [2d] all_totals = new int[0 : Ti.numProcs() - 1][2d];
	boolean[1d] single [1d] all_use_book = 
	    new boolean[0:Ti.numProcs()-1][1d];
	int[1d] weight0, profit0;
	int my_books, my_start_book, my_end_book;
	rand = new Random();
	n_blocks = Ti.numProcs();
	 
	//get_opts (args);
	books_per_proc = (n_books + Ti.numProcs() - 1) / Ti.numProcs();
	my_books = ((Ti.numProcs() - 1 == Ti.thisProc()) && 
		    (n_books % books_per_proc != 0)) ? 
	    (n_books % books_per_proc) : books_per_proc;
	my_start_book = books_per_proc * Ti.thisProc();
	my_end_book = my_start_book + my_books - 1;
	debug("" + my_books, 1);

	cap_per_block = (bag_cap + 1) / n_blocks;
	//System.out.println("cap per block: " + cap_per_block);
	
	try {
	    weight = new int[0:n_books-1];
	    profit = new int[0:n_books-1];
	    if (Ti.thisProc() != 0)
		use_book = new boolean[my_start_book:my_end_book];
	    else
		use_book = new boolean[0:n_books-1];
	} catch (OutOfMemoryError e) {
	    System.err.println( "Insufficient memory for " + n_books + 
				" books with max. capacity " + bag_cap);
	    System.exit(1);
	}
	
	if (Ti.thisProc() == 0) {
	    solve_timer = new Timer();
	    backtrack_timer = new Timer();
	    init_books ();
	}	
 
	try {
	  total = new int[my_start_book-1:my_end_book, 0:bag_cap];
	  //if (Ti.thisProc() == 0) {
	  //	total_total = new int[0:n_books-1, 0:bag_cap];
	  //}
	} catch (OutOfMemoryError e) {
	  System.err.println("Insufficient memory for profit table");
	  System.exit(1);
	}

	// Send data out to all processors.
	all_totals.exchange(total);
	all_use_book.exchange(use_book);
	weight0 = broadcast weight from 0;
	profit0 = broadcast profit from 0;
	if (Ti.thisProc() != 0) {
	    weight.copy(weight0);
	    profit.copy(profit0);
	}
	Ti.barrier();

	if (Ti.thisProc() == 0) {
	    solve_timer.reset();
	    backtrack_timer.reset();
	}
	
	if (Ti.thisProc() == 0) {
	    solve_timer.start();
	}
	total_profit = solve ((int single) n_books, (int single) bag_cap, 
			      weight, profit, total, all_totals, my_books, 
			      my_start_book, my_end_book, 
			      (int single) n_blocks);
	if (Ti.thisProc() == 0) {
	    solve_timer.stop();
	}
	
	debug("G", 1);

	// For now, only proc 0 backtracks

	if (Ti.thisProc() == 0) {
	    System.out.println("Total profit: " + total_profit);
	    System.out.println("Max book weight: " + max_random_weight);
	    System.out.println("Max book profit: " + max_random_profit);
	    //System.out.println("Times: solve " + solve_timer.secs() + ", backtrack " + backtrack_timer.secs());
	}
	return;
    }
    
    static inline int getTotal(int[1d][2d] totals, int i, int j) {
	debug(i + " " + j, 4);
	return totals[i / books_per_proc][i,j];
    }

    static inline int getTotal(int[2d] local total, int i, int j) {
	return total[i,j];
    } 

    static inline void writeTotal(int[2d] local total, int i, int j, 
				  int value) {
	total[i,j] = value;
    }

    static inline int min(int x, int y) {
	return x > y ? y : x;
    }

    static inline int max(int x, int y) {
	return x > y ? x : y;
    }

    static inline void copyTotal(int[1d][2d] totals, int[2d] local mytotals, 
				 int book, int start_cap, int end_cap) {
	int proc = book / books_per_proc;
	mytotals.copy(totals[proc], [[book,start_cap]:[book,end_cap]]);
    }


    static final int DEBUG_LEVEL = 0;

    static single int solve (int single n_books, int single bag_cap, 
			     int[1d] local weight, int[1d] local profit, 
			     int[2d] local total, int[1d][2d] all_totals, 
			     int my_books, int my_start_book, int my_end_book, 
			     int single n_blocks) {
	int book_i;
	int cap_j;
	int single iter;
	int start_iter, end_iter;
	int block_no;
	int my_start_cap, my_end_cap;
	debug("books: " + my_start_book + " " + my_end_book, 1);
	if (Ti.thisProc() == 0) {
	    for (cap_j = 0; cap_j <= bag_cap; ++cap_j) {
		if (weight[0] > cap_j)
		    /* Doesn't fit. */
		    writeTotal(total, 0, cap_j, 0);
		else
		    writeTotal(total, 0, cap_j, profit[0]);
	    }
	    my_start_book++;
	}
	debug("A", 1); 
	start_iter = Ti.thisProc();
	end_iter = Ti.thisProc() + n_blocks - 1;
	debug(start_iter + " " + end_iter, 1); 
	for (iter = 0; iter < Ti.numProcs() + n_blocks - 1; ++iter) {
	    Ti.barrier();
	    debug("B " + iter, 2);
	    if (start_iter <= iter && end_iter >= iter) {
		debug("D", 2);
		block_no = iter - Ti.thisProc();
		my_start_cap = block_no * cap_per_block;
		my_end_cap = (block_no == n_blocks - 1 ? bag_cap : 
			      my_start_cap + cap_per_block - 1); 
		if (Ti.thisProc() != 0) {
		    copyTotal(all_totals, total, my_start_book-1, 
			      my_start_cap, my_end_cap);
		}
		for (book_i = my_start_book; book_i <= my_end_book; book_i++) {
		    for (cap_j = my_start_cap; cap_j <= my_end_cap; cap_j++) {
			int new_profit;
			// THIS IS THE PROBLEM DEBUG CALL
			debug("E " + iter + " " + cap_j + " " + book_i, 3);
			if (cap_j < weight[book_i]) {
			    /* Doesn't fit. */
			    writeTotal(total, book_i, cap_j, 
				       getTotal(total, book_i - 1, cap_j));
			    continue;
			}
			new_profit = profit[book_i] + 
			    getTotal(total, book_i-1, cap_j-weight[book_i]);
			writeTotal(total, book_i, cap_j, 
				   max(getTotal(total, book_i-1, cap_j), 
				       new_profit)); 
		    }
		}
	    }
	}
	Ti.barrier();
	debug("C", 1);
	return getTotal(all_totals, n_books-1, bag_cap);
    }	
    

    static final int STATIC = 0;
    static final int READFILE = 1;
    static final int RANDOM = 2;
    static int init_from = STATIC;
    static String fname;
    static int max_random_weight = DEFAULT_max_random_weight;
    static int max_random_profit = DEFAULT_max_random_profit;
    static long seedval = -1;
    static Random rand;

    static void init_books () {
	switch (init_from) {
	case STATIC:
	    staticgen_books (n_books, weight, profit);
	    break;
	case RANDOM:
	    randgen_books (seedval, n_books, weight, profit);
	    break;
	default:
	    System.err.println("Unknown initialization routine.");
	    System.exit(1);
	}
    }

    static void randgen_books_ (int n, int[1d] weight, int[1d] profit) {
      int k;
      double x;
      
      for (k = 0; k < n; ++k) {
	weight[k] = 1 + (int)(max_random_weight * rand.nextDouble());
	profit[k] = 1 + (int)(max_random_profit * rand.nextDouble());
      }
    }
    
    static void randgen_books (long seedval, int n, int[1d] weight, int[1d]
profit) {
      if (seedval < 0)
	seedval = 1010101L;
	// seedval = (long) clock();
      // srand48(seedval);
      rand.setSeed(seedval);
    }

    static void staticgen_books (int n, int[1d] weight, int[1d] profit) {
      rand.setSeed(1010101L);
      // srand48 (1010101L);
      randgen_books_ (n, weight, profit);
    }
}