背包问题

暴力实现 #

public static int maxValue(int[] w, int[] v, int bag) {
  if (w == null || v == null || w.length != v.length || w.length == 0) return 0;
  return process(w, v, 0, bag); // 递归调用的子过程
}

private static int process(int[] w, int[] v, int index, int rest) {
  if (rest < 0) return -1; // 背包容量不够了，本次是失败的 返回-1
  if (index == w.length) return 0; // 所有货物装完的情况 没有东西可以装了
  int p1 = process(w, v, index + 1, rest);
  int p2 = 0;
  int next = process(w, v, index + 1, rest - w[index]);
  if (next != -1) p2 = v[index] + next; // 如果 返回值是-1 则代表容量超了
  return Math.max(p1, p2); // 返回最好的情况（价值最高）
}

DP(从左到右的尝试模型) #

根据状态转移方程（暴力递归的子过程）建立缓存，实现 DP

每一行依赖它的下一行，列无要求

public static int dp(int[] w, int[] v, int bag) {
  if (w == null || v == null || w.length != v.length || w.length == 0) return 0;
  int N = w.length;
  int[][] dp = new int[N + 1][bag + 1];
  for (int index = N - 1; index >= 0; index--) {
    for (int rest = 0; rest <= bag; rest++) {
      int p1 = dp[index + 1][rest];
      int p2 = 0;
      int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
      if (next != -1)
        p2 = v[index] + next;
      dp[index][rest] = Math.max(p1, p2);
    }
  }
  return dp[0][bag];
}