Knapsack

This is the first DP algorithm I learned when I started learning algorithm at the first time. I was so stupid back then that I didn't know what the matrix really means, so I literally wrote a code and "calculated" the matrix.

Uh, those time...

Ok, back to the problem.

The version of the question I learned back then is that a thief is breaking into a museum. He has a bag that can carry at most weight W. There are n items in the museum[0, ...i, ... n - 1]. Each is weighted w_i and has value v_i. None of the items can be broken down to pieces. The thief needs to decide which items to carry in order to get the maximum value.

Yeah, we are trying to help a crime... -_-

As we mentioned, the solution is a DP approach. So how to build the matrix?
If we break down the problems to 1 item and weight w, then if the item is heavier than weight, the thief cannot carry it, then the remaining weight will be w - w_1. Let's assume we can carry the item 1. Now if we add one more item, we either choose to carry the item 2, and the remaining weight will be w _ w_1 - w_2, and the value will be v_1 + v_2. Or we choose not to carry it, then there is only item 1 in the bag. Yup, it is Max(bag[i - 1][w], bag[i - 1][w - w_[i - 1]] + v[i - 1]).

public static int maxValue(int[] value, int[] weight, int maxW) {
  if (value == null || weight == null || value.length != weight.length)
   throw new NullPointerException("Invalid input!");
  int[][] values = new int[value.length + 1][maxW + 1];
  for (int i = 1; i <= value.length; i++) {
   for (int w = 1; w <= maxW; w++) {
    if (weight[i - 1] <= w) {
     values[i][w] = Math.max(values[i - 1][w], values[i - 1][w - weight[i - 1]] + value[i - 1]);
    }
    else
     values[i][w] = values[i - 1][w];
   }
  }
  return values[value.length][maxW];
 }