背包问题 二维
题目链接：背包问题 二维
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰背包问题 二维
日期：2024-10-09
想法：dp[i][j]，i表示需要从物品0-i中选择加入到背包中，j表示背包的容量，dp值表示最大的价值；
递推公式，如果背包大小j都比此时要放的物品i的weight[i]小了，背包放不下物品i了，此时最大的价值就是上一个物品i-1的最大价值了即dp[i-1][j]; j>weight[i]时，j-weight表示将此时i的重量腾出来，而此时dp[i - 1][j-weight]大小就是空出物品i空间后的最大价值，加上value[i]就知道了dp[i][j]的一个可能值，当然还要跟dp[i-1][j]比一下大小，如果放了物品i价值更低了呢，所以递推公式就是dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
初始化j=0时背包放不了任何东西，价值为0，即dp二维数组第一列初始化为0，第一行背包容量大于等于weight[0]时才能将物品0放入背包，即放入价值value[0]，否则都是价值0；
遍历顺序：第一行第一列都初始化好了，从i=1，j=1开始，最后返回dp右下角值就行了
Java代码如下：
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int M = scanner.nextInt();
int bagweight = scanner.nextInt();
int[] weight = new int[M];
int[] value = new int[M];
for(int i = 0; i < M; i++) {
weight[i] = scanner.nextInt();
}
for(int j = 0; j < M; j++) {
value[j] = scanner.nextInt();
}
int[][] dp = new int[M][bagweight + 1];
for(int i = weight[0]; i <= bagweight; i++) {
dp[0][i] = value[0];
}
for(int i = 1; i < M; i++) {
for(int j = 1; j <= bagweight; j++) {
if(weight[i] > j) {
dp[i][j] = dp[i - 1][j];
}else {
dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
}
}
}
System.out.println(dp[M - 1][bagweight]);
}
}
背包问题 一维
题目链接：背包问题 一维
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰背包问题 一维
日期：2024-10-09
想法：注意到二维数组的每一行的更新都是从上一行来的（都有个i - 1），那么只在同一行操作就能降低一维即递归变成：dp[j] = Math.max(dp[j - weight[i]] + value[i], dp[j])同样能达成目的。
Java代码如下：
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int M = scanner.nextInt();
int bagweight = scanner.nextInt();
int[] weight = new int[M];
int[] value = new int[M];
for(int i = 0; i < M; i++) {
weight[i] = scanner.nextInt();
}
for(int j = 0; j < M; j++) {
value[j] = scanner.nextInt();
}
int[] dp = new int[bagweight + 1];
for(int i = 0; i < M; i++) {
for(int j = bagweight; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j - weight[i]] + value[i], dp[j]);
}
}
System.out.println(dp[bagweight]);
}
}
总结：第一次写成了下面代码那样，对于背包容量依旧从小到大来，在背包只能放一个物品的时候没问题，但如果背包大小为2，物品0大小为1，我在设置背包容量为1的时候装了一次了即dp[1] = value[0]； 而到背包容量为2时计算dp[j - weight[i]] + value[i]，这个dp[j - weight[i]] = dp[1]，意思就是我会再装一次物品0来得到价值最大，这于物品放一次就不符合了，所以只能倒着遍历背包容量从j = bagweight开始，j >= weight[i]时就进入遍历公式，此时的dp[j - weight[i]] + value[i]依旧用的是之前没有变动过的数据，才能得到正确答案
import java.util.Scanner;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int M = scanner.nextInt();
int bagweight = scanner.nextInt();
int[] weight = new int[M];
int[] value = new int[M];
for(int i = 0; i < M; i++) {
weight[i] = scanner.nextInt();
}
for(int j = 0; j < M; j++) {
value[j] = scanner.nextInt();
}
int[] dp = new int[bagweight + 1];
for(int i = 0; i < M; i++) {
for(int j = 1; j <= bagweight; j++) {
if(weight[i] > j) {
continue;
}else {
dp[j] = Math.max(dp[j - weight[i]] + value[i], dp[j]);
}
}
}
System.out.println(dp[bagweight]);
}
}
416. 分割等和子集
题目链接：416. 分割等和子集
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰分割等和子集
日期：2024-10-09
想法：背包问题初遇还是挺难的，此题中背包容量为target = sum / 2，物品i大小为nums[i]，价值也是nums[i]，最后判断dp[target] == target，等于就能找到。
Java代码如下：
class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0) return false;
int sum = 0;
for(int num : nums) {
sum += num;
}
if(sum % 2 != 0) {
return false;
}
int target = sum / 2;
int[] dp = new int[target + 1];
for(int i = 0; i < nums.length; i++) {
for(int j = target; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if(dp[target] == target) {
return true;
}else return false;
}
}