Knapsack 0/1

1int knapsack(int[] wt, int[] val, int W) {2  int n = wt.length;3  int[][] dp = new int[n + 1][W + 1];  // hàng 0 toàn số 04  for (int i = 1; i <= n; i++)5    for (int w = 0; w <= W; w++) {6      dp[i][w] = dp[i-1][w];  // bỏ qua vật phẩm i7      if (wt[i-1] <= w)8        dp[i][w] = Math.max(dp[i][w],9            val[i-1] + dp[i-1][w - wt[i-1]]);  // lấy nó — cộng giá trị10    }11  return dp[n][W];12}