做网站网站危险吗,搜一下百度,家具展示网站源码,37网页游戏中心文章目录 day36#xff1a;动态规划part4#xff0c;背包问题01背包416.分割等和子集 day36#xff1a;动态规划part4#xff0c;背包问题
01背包
https://kamacoder.com/problempage.php?pid1046
二维数组版本#xff1a;
dp[i][j]里的i和j表达的是什么了#xff0… 文章目录 day36动态规划part4背包问题01背包416.分割等和子集 day36动态规划part4背包问题
01背包
https://kamacoder.com/problempage.php?pid1046
二维数组版本
dp[i][j]里的i和j表达的是什么了i是物品j是背包容量。
dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
import java.util.*;class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int m in.nextInt();int n in.nextInt();int[] values new int[m];int[] weights new int[m];for (int i 0; i m; i) weights[i] in.nextInt();for (int i 0; i m; i) values[i] in.nextInt();int[][] dp new int[m][n 1];for (int i weights[0]; i n; i) dp[0][i] values[0];for (int i 1; i m; i) {for (int j 1; j n; j) {if (j weights[i])dp[i][j] dp[i - 1][j];elsedp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] values[i]);}}System.out.println(dp[m - 1][n]);}
}压缩为一维滚动数组版本
dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。
import java.util.*;class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int m in.nextInt();int n in.nextInt();int[] values new int[m];int[] weights new int[m];for (int i 0; i m; i) weights[i] in.nextInt();for (int i 0; i m; i) values[i] in.nextInt();int[] dp new int[n 1];for (int i 0; i m; i) {for (int j n; j weights[i]; j--)dp[j] Math.max(dp[j], dp[j - weights[i]] values[i]);}System.out.println(dp[n]);}
}416.分割等和子集
01背包应用
class Solution {public boolean canPartition(int[] nums) {int n nums.length;int sum 0;for (int num : nums) sum num;if (sum % 2 1) return false;int target sum / 2;int[] dp new int[target 1];for (int i 0; i n; 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;}return false;}
}
