本文主要是介绍代码随想录day36:动态规划part4,背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- day36:动态规划part4,背包问题
- 01背包
- 416.分割等和子集
day36:动态规划part4,背包问题
01背包
https://kamacoder.com/problempage.php?pid=1046
二维数组版本:
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;}
}
这篇关于代码随想录day36:动态规划part4,背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!