背包问题

package com.atguigu.dynamic;
import java.util.Arrays;
/**
 * 动态规划 --- 背包问题
 *
 * @author Dxkstart
 * @create 2022-04-12-16:13
 */
public class KnapsackProblem {
    public static void main(String[] args) {
        // 物品的重量
        int[] w = {1,4,3};
        // 物品的价值
        int[] v = {1500,3000,2000};
        // 背包容量
        int m = 4;
        // 物品的总数
        int n = v.length;
        // 一个二维数组表
        int[][] arr = new int[n+1][m+1];
        // 初始化第一行第一列，都为0
        for (int i = 0; i < m + 1; i++) {
            arr[0][i] = 0;
        }
        for (int i = 0; i < n + 1; i++) {
            arr[i][0] = 0;
        }
        // 根据公式进行动态规划处理
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                // 物品的重量 > 此时的背包容量  => 同一列的上一个格子的值
                // 公式：arr[i][j] = arr[i-1][j]
                if (w[i-1] > j) {
                    arr[i][j] = arr[i-1][j];
                }
                // 此时的背包容量 >= 物品的重量
                // 公式： arr[i][j] = max{ arr[i-1][j], v[i-1] + arr[i-1][j-w[i-1]] }
                if (j >= w[i-1]) {
                    // 同一列的上一格
                    int a = arr[i-1][j];
                    int b = v[i-1] + arr[i-1][j-w[i-1]];
                    arr[i][j] = a > b ? a : b;
                }
            }
        }
        // 输出矩阵
        for (int[] in: arr) {
            System.err.println(Arrays.toString(in));
        }
    }
}