/** * weight[] = {2,3,4,5} * value[] = {3,4,5,7} * 求解满足小于背包最大承重得到最大价值的物品存放策略 * 思路核心: * 1. 当前取物品的重量weight[i-1] <= j 当前能取最大重量 * 2. 比较价值：不放这个物品的最高价值 和 放入此物品的最高价值 * maxValue[i-1][j] 不放这个物品的最高价值 * value[i-1] + maxValue[i-1][j-weight[i-1]] 当前物品价值 + 放入当前物品的前i-1个物品的最高价值 * ------------------------------------------------------- * ｜ i\j ｜ 0 ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 9 ｜ * ------------------------------------------------------- * ｜ 0 ｜ 0 ｜ 0 ｜ 0 ｜ 0 ｜ 0 ｜ 0 ｜ 0 ｜ 0 ｜ 0 ｜ 0 ｜ * ------------------------------------------------------- * ｜ 1 ｜ 0 ｜ 0 ｜ 3 ｜ 3 ｜ 3 ｜ 3 ｜ 3 ｜ 3 ｜ 3 ｜ 3 ｜ * ------------------------------------------------------- * ｜ 2 ｜ 0 ｜ 0 ｜ 3 ｜ 4 ｜ 4 ｜ 7 ｜ 7 ｜ 7 ｜ 7 ｜ 7 ｜ * ------------------------------------------------------- * ｜ 3 ｜ 0 ｜ 0 ｜ 3 ｜ 4 ｜ 5 ｜ 7 ｜ 8 ｜ 9 ｜ 9 ｜ 12 ｜ * ------------------------------------------------------- * ｜ 4 ｜ 0 ｜ 0 ｜ 3 ｜ 4 ｜ 5 ｜ 7 ｜ 8 ｜ 10｜ 11｜ 12 ｜ * ------------------------------------------------------- * eg: * i=3,j=2; * weight[3-1] = 4 > j -----> maxValue[3-1][2] = maxValue[2-1][2] = 3 * * i=3,j=4; * weight[3-1] = 4 <= j 成立 * maxValue[3-1][4] = 4 不放这个物品的最高价值 * value[3-1] + maxValue[2][4-4] =5 + 0 = 5 > 4 当前物品价值 + 放入当前物品的前i-1个物品的最高价值 */ public static int getMaxValue(int[] weight, int[] value, int maxWeight) { int n = weight.length;//物品数目 // 定义最大价值二维数组，从0开始，各维度需加一个长度 int[][] maxValue = new int[n + 1][maxWeight + 1]; // 最大重量和物品数为0，价值为0 for (int w = 0; w < maxWeight + 1; w++) { maxValue[0][w] = 0; } for (int i = 0; i < n + 1; i++) { maxValue[i][0] = 0; } // 只拿前i件物品（最大价值从0开始，对应的weight和value取i-1） for (int i = 1; i <= n; i++) { for (int j = 1; j <= maxWeight; j++) { // 先假定当前物品的最大价值等于放上一件的最大价值 maxValue[i][j] = maxValue[i - 1][j]; // 当前物品的重量小于等于总重量 if (weight[i - 1] <=j) { // 比较 不放这个物品的最高价值 和 放入此物品的最高价值 if (value[i - 1] + maxValue[i - 1][j - weight[i - 1]] > maxValue[i - 1][j]) { maxValue[i][j] = value[i - 1] + maxValue[i - 1][j - weight[i - 1]]; } } } } return maxValue[n][maxWeight]; } public static void main(String[] args){ int weight[]={2,3,4,5}; int value[]={3,4,5,7}; int maxWeight=9; System.out.println(getMaxValue(weight,value,maxWeight)); }