Knapsack

The knapsack problem ZeroOneKnapsack.java

  public static int knapsack(int w, List<Pair<Integer, Integer>> items) {
    int[] V = new int[w + 1];
    for (Pair<Integer, Integer> item : items) {
      for (int j = w; j >= item.getFirst(); --j) {
        V[j] = Math.max(V[j], V[j - item.getFirst()] + item.getSecond());
      }
    }
    return V[w];
  }