1. 动态规划--背包问题

1. 背包问题：有一个背包，容量为4磅 ， 现有如下物品

1)要求达到的目标为装入的背包的总价值最大，并且重量不超出
2)要求装入的物品不能重复

2. 过程分析

动态规划的核心思想：当前的决策是基于之前的决策基础之上的。所以背包的重量不断增加，直至最大值

step1: 当背包的容量为0时，任何物品都装不了；同理，当没有任务物品时，不管背包容量多大，其实际什么也都装不了。所以实际为：

step2: 当物品只有吉他时，对于不同容量的背包，其实际可能装的物品只有吉他，所以：

step3: 当物品有吉他和音箱时，不同容量的背包，可装的物品有：(也只有当容量为4的时候，才有必要考虑延用之前的策略，还是用替换为当前4磅的商品)

step4: 当可选物品中有吉他、音箱、电脑时，对应不同容量的背包，其选择策略是：
（注：背包是4磅时，可以参考3磅的情况。延用3磅的结果，还剩1磅的容量，此时正好满足吉他，并且其总价值大于之前4磅的所有选择）

动规的体现：1）（{吉他，音箱，电脑}，4）参考了（{吉他，音箱，电脑}，3）；
2）（{吉他，音箱，电脑}，4） 对比了（{吉他，音箱}，4）

3. 逻辑汇总

4. demo

public class Main1 {
  public static void main(String[] args) throws UnsupportedEncodingException {
    //     新建数组，保存物品的重量
    int[] weight = {1, 4, 3};
    //      物品的价值
    int[] value = {1500, 3000, 2000};
    int m = 4; // 背包的容量
    int n = value.length; // 物品的个数
    // v[i][j] 表示在有i个物品中，能够装入容量为j的背包中的最大物品价值之和
    int[][] v = new int[n + 1][m + 1];
    // 初始化第一行第一列全部为0
    for (int i = 0; i < v.length; i++) {
      v[i][0] = 0;
    }
    for (int j = 0; j < v[0].length; j++) {
      v[0][j] = 0;
    }
    // 根据公式来动态规划处理
    for (int i = 1; i < v.length; i++) { // 商品
      for (int j = 1; j < v[i].length; j++) { // 背包容量
        if (weight[i - 1] > j) { // 当前商品的容量大于了背包的总容量，所以延用之前的策略
          v[i][j] = v[i - 1][j];
        } else {
          // 因为此代码中的i是从1开始的，所以value,weight数组中的下标都需要-1
          v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]);
        }
        System.out.print(v[i][j] + " ");
      }
      System.out.println();
    }
  }
}

5. 记录存放的商品

public class Main1 {
  public static void main(String[] args) throws UnsupportedEncodingException {
    //     新建数组，保存物品的重量
    int[] weight = {1, 4, 3};
    //      物品的价值
    int[] value = {1500, 3000, 2000};
    int m = 4; // 背包的容量
    int n = value.length; // 物品的个数
    // v[i][j] 表示在有i个物品中，能够装入容量为j的背包中的最大物品价值之和
    int[][] v = new int[n + 1][m + 1];

    // 初始化第一行第一列全部为0
    for (int i = 0; i < v.length; i++) {
      v[i][0] = 0;
    }
    for (int j = 0; j < v[0].length; j++) {
      v[0][j] = 0;
    }

    // 为了记录商品存放的情况，我们定义一个二维数组
    int[][] records = new int[n + 1][m + 1];

    // 根据公式来动态规划处理
    for (int i = 1; i < v.length; i++) { // 商品
      for (int j = 1; j < v[i].length; j++) { // 背包容量
        if (weight[i - 1] > j) { // 当前商品的容量大于了背包的总容量，所以延用之前的策略
          v[i][j] = v[i - 1][j];
        } else {
          // 因为此代码中的i是从1开始的，所以value,weight数组中的下标都需要-1
          //          v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]);
          // 为了记录商品存放情况，改写v[i][j]
          if (v[i - 1][j] > value[i - 1] + v[i - 1][j - weight[i - 1]]) {
            v[i][j] = v[i - 1][j];
            // 延用了之前的策略，所以不做“商品添加”的记录
          } else {
            v[i][j] = value[i - 1] + v[i - 1][j - weight[i - 1]];
            records[i][j] = 1; // 当前有新商品添加
          }
        }
        System.out.print(v[i][j] + " ");
      }
      System.out.println();
    }

    System.out.println("================打印存放的商品清单=======================");
    int i = records.length - 1;
    int j = records[0].length - 1;
    while (i > 0 && j > 0) {
      if (records[i][j] == 1) {
        System.out.printf("第%d个商品放入\n", i);
        j -= weight[i - 1];
      }
      i--;
    }
  }
}