- 1.描述
- 2.代码
- 1.动态规划
- code
- 复杂度
- 2.动态规划&空间优化
- code
- 复杂度
【0-1背包问题】有一个背包,容量是W=120,有7个物品,物品不可分割。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
物品: A B C D E F G
重量:30 30 60 55 40 10 25
价值:10 40 30 50 35 40 30
2.代码 1.动态规划 codepublic int knapsackWithDp(int capacity, int[] weights, int[] values) { int n = weights.length; int[][] dp = new int[n + 1][capacity + 1]; for (int i = 1; i <= n; i++) { for (int j = 0; j <= capacity; j++) { if (j >= weights[i - 1]) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n][capacity]; }复杂度
* 时间复杂度 O(nW) W为背包容量取值范围 * 空闲复杂度 O(nW) W为背包容量取值范围2.动态规划&空间优化 code
public int knapsackWithDpSpaceOpt(int capacity, int[] weights, int[] values) { int n = weights.length; int[] dp = new int[capacity + 1]; for (int i = 1; i <= n; i++) { for (int j = capacity; j > 0; j--) { if (j >= weights[i - 1]) { dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]); } } } return dp[capacity]; }复杂度
* 时间复杂度 O(nW) W为背包容量取值范围 * 空间复杂度 O(W) W为背包容量取值范围
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)