Day 39 || 01背包、416. 分割等和子集

01背包

题目链接：卡码网第46题

二维解题思路：需要建立一个i行k列的dp数组，i表示每个物品，k代表容量，初始化数组子一列为0，第一行从背包开始能够放入起始为价值，其他都为0。for双循环先背包后物品，还是先物品后背包都可以。主要代码：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + value);

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int kind = scanner.nextInt(); // 研究材料的种类数int size = scanner.nextInt(); // 小明的行李空间int[] weights = new int[kind]; // 每种材料的占用空间int[] values = new int[kind];  // 每种材料的价值// 读取占用空间for (int i = 0; i < kind; i++) {weights[i] = scanner.nextInt();}// 读取价值for (int i = 0; i < kind; i++) {values[i] = scanner.nextInt();}// 定义dp数组int[][] dp = new int[kind + 1][size + 1];// 动态规划求解背包问题for (int i = 1; i <= kind; i++) {int weight = weights[i - 1];int value = values[i - 1];for (int j = 0; j <= size; j++) {if (j < weight) {dp[i][j] = dp[i - 1][j]; // 当前物品无法放入} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + value); // 选择放或不放}}}// 输出结果System.out.println(dp[kind][size]); // 背包最大价值scanner.close();}
}

一维解题思路：需要建立一个k大小的的dp数组，k代表容量，初始化数组子一列为0，背包倒序计算内部最大价值，即从大容量向小容量计算，因为从小容量向大容两计算的时候 dp[i - 1][j - weight] + value可能重复计算当前物品已经放入过的情况。双层for循环，先物品后背包倒序循环。主要代码：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight] + value);

416. 分割等和子集

题目链接：力扣题目链接

思路：背包大小就是整个数组的之和的一半，如果是奇数不成立。然后想象成大小和价值一样，容量就是数组之和的一半即可。