Knapsack { public static int mostValue(HashMap<Integer, Integer> map, int total) { int[] weights = map.keySet().stream().mapToInt(Integer::intValue).toArray(); int[][] dp = new int[weights.length][total + 1]; for (int i = 0; i < weights.length; i++) { dp[i][0] = 0; } for (int i = 1; i <= total; i++) { if (i < weights[0]) { dp[0][i] = 0; } else { dp[0][i] = map.get(weights[0]); } } for (int i = 1; i < weights.length; i++) { for (int j = 1; j <= total; j++) { if (j < weights[i]) { dp[i][j] = dp[i][j - 1]; } else { int v = map.get(weights[i]); dp[i][j] = Integer.max(dp[i - 1][j - weights[i]] + v, dp[i - 1][j]); } } } return dp[weights.length - 1][total]; }  static int mostValue(HashMap<Integer, Integer> map, int total);  }
@Test(dataProvider = "knapsackDataProvider") public void test(HashMap<Integer, Integer> map, int total, int expected) { assertEquals(Knapsack.mostValue(map, total), expected); }