代码随想录day30：动态规划part3

二维数组0-1背包

- 关于dp数组的定义问题，up是先给dp数组，再推递推关系。实际上应该先搞清楚问题与子问题之间的递推关系，在定义dp数组。

- 首先对于整个问题：m个物品，背包容量最大为n。

- 初步将问题分解为：在已经知道了前m-1个物品的所有最优解的情况下（即无论背包容量多少），再加上第m个物品的情况。

- 此时有三种情况：

- 1、第m个的重量超过了背包容量n，不可能放下第m个，所以此时的最优解，就是m-1个物品，背包容量为n的最优解。

- 2、第m个的重量小于n，可以放但是不放，此时的最优解仍然是m-1个物品，背包容量为n的最优解。

- 3、第m个的重量小于n，可以放而且真的放了，此时最优解就是第m个物品的价值，加上，m-1个物品时背包容量为（n-第m个物品的重量）的最优解。

当i放进去时，那么这时候整个物品集就被分成两部分，1到i-1和第i个，而这是i是确定要放进去的，那么就把j空间里的wi给占据了，只剩下j－wi的空间给前面i－1，那么只要这时候前面i－1在j－wi空间里构造出最大价值，即dp【i－1】【j－wi】，再加上此时放入的i的价值vi，就是dpij了

int knapsackDP(int[] wgt, int[] val, int cap) {int n = wgt.length;// 初始化 dp 表int[][] dp = new int[n + 1][cap + 1];// 状态转移for (int i = 1; i <= n; i++) {for (int c = 1; c <= cap; c++) {if (wgt[i - 1] > c) {// 若超过背包容量，则不选物品 idp[i][c] = dp[i - 1][c];} else {// 不选和选物品 i 这两种方案的较大值dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);}}}return dp[n][cap];
}

  01背包每个背包都只有一个，这个包放于不放与上一个包的状态有关，而左边的数组是描述上一个包状态的量，右边的数是当前包状态的一个待定，代码里就是右边数组的确定需要左边的数，所以在计算出右边的数之前不能破坏左边的数； 完全背包每种背包不止一个，这个包放与不放也取决于上一个包，而上一个包可以和当前包相同，所以需要从左向右遍历。

/* 0-1 背包：空间优化后的动态规划 */
int knapsackDPComp(int[] wgt, int[] val, int cap) {int n = wgt.length;// 初始化 dp 表int[] dp = new int[cap + 1];// 状态转移for (int i = 1; i <= n; i++) {// 倒序遍历for (int c = cap; c >= 1; c--) {if (wgt[i - 1] <= c) {// 不选和选物品 i 这两种方案的较大值dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);}}}return dp[cap];
}

416. 分割等和子集

class Solution {public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0) return false;int n = nums.length;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 = 1; i <= n; i++) {for(int j = target; j >= nums[i - 1]; j--) {//物品 i 的重量是 nums[i]，其价值也是 nums[i]dp[j] = Math.max(dp[j], dp[j - nums[i -1]] + nums[i -1]);}//剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）if(dp[target] == target)return true;}return dp[target] == target;}
}