public int backPackIII(int[] A, int[] V, int m) {

if (A == null || V == null || A.length != V.length) {

return 0;

}

int n = A.length;

int[][] dp = new int[n + 1][m + 1]; // max value with i items of weight w.

for (int j = 0; j <= m; j++) {

dp[0][j] = -1; // 0 items cannot form j weight, hence value = 0

}

dp[0][0] = 0;

for (int i = 1; i <= n; i++) {

for (int j = 0; j <= m; j++) { // for all weight j at i items

for (int k = 0; k * A[i - 1] <= m; k++) {

if (j - k * A[i - 1] >= 0 && dp[i - 1][j - k * A[i - 1]] != -1) {

dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]);

}

}

}

}

int rst = 0;

for (int j = 0; j <= m; j++) {

rst = Math.max(rst, dp[n][j]);

}

return rst;

}

public int backPackIII(int[] A, int[] V, int m) {

if (A == null || V == null || A.length != V.length) {

return 0;

}

int n = A.length;

int[][] dp = new int[n + 1][m + 1]; // max value with i items of weight w.

for (int j = 0; j <= m; j++) {

dp[0][j] = -1; // 0 items cannot form j weight, hence value = 0

}

dp[0][0] = 0;

for (int i = 1; i <= n; i++) {

for (int j = 0; j <= m; j++) { // for all weight j at i items

dp[i][j] = dp[i - 1][j];

if (j - A[i - 1] >= 0) {

dp[i][j] = Math.max(dp[i][j], dp[i][j - A[i - 1]] + V[i - 1]);

}

}

}

int rst = 0;

for (int j = 0; j <= m; j++) {

rst = Math.max(rst, dp[n][j]);

}

return rst;

}