Leetcode-day31-01背包问题

46. 携带研究材料

1.dp数组代表的是什么？ 这里的dp数组是一个二维数组，dp[i][j]是从前i个物品中任选放入容量j内的最大价值。

2.递推公式。

• 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。

• 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.dp数组初始化：dp数组的第一列，也就是容量为0，此时都是0。dp数组的第一行，也就是把第0个物品放入，此时前面都是0（放不进去的时候），直到能放进去了变为value[i]。

4.遍历方向，外层是背包或者外层是物品都可以

5.打印dp数组，最右下角的元素

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int bagweight = scanner.nextInt();int[] weight = new int[n];int[] value = new int[n];for (int i = 0; i < n; ++i) {weight[i] = scanner.nextInt();}for (int j = 0; j < n; ++j) {value[j] = scanner.nextInt();}int[][] dp = new int[n][bagweight + 1];for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}for (int i = 1; i < n; i++) {for (int j = 0; j <= bagweight; j++) {if (j < weight[i]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}System.out.println(dp[n - 1][bagweight]);}
}