背包问题（一）--01背包
01背包模型问题
背包容量为V，有N件物品，每件物品的体积是vi，价值是wi，每件物品最多使用一次。求将哪些物品装入背包，得到的价值最大
思路
利用子问题定义状态进行求解。f(i,v)表示取前i件物品恰好放入容量小于等于v的背包可以获得的最大价值，则
f(i,v) = max( f( i-1 , v ) , f( i-1，v-vi ) + wi )
f(i,v)状态可以转化为只考虑第i件物品：
如果选择第i件物品，那么此时的价值就是f(i-1,v-vi)+wi，f(i-1,v-vi)即将前i-1件物品放入容量小于等于v-vi的背包的最大价值
如果不选择第i件物品，那么此时的价值就是f(i-1,v),即将前i-1件物品放入容量小于等于v的背包的最大价值
只需要选择两者中最大的那个就是f(i,v)的状态了
最终答案就是f(N,V)，即取前N件物品放入容量小于等于V的背包中的最大价值
代码实现
public static void main(String[] args){
// 读取数据
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N+1];
int[] w = new int[N+1];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
// 01背包
int[][] dp = new int[N+1][V+1];
// dp[0][0...V] 默认为0
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i-1][j];
if (j >= v[i]) {
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
}
}
System.out.println(dp[N][V]);
}
记录最大价值时选中的商品
// 如果需要记录物品是否被选中，可以使用一个二维数组记录物品状态，path[i][j]
// f(i,v) = max( f( i-1 , v ) , f( i-1，v-vi ) + wi )
// 如果f( i-1 , v)比较大，path[i][v] = 0
// 如果f( i-1 , v - vi ) + wi比较大，path[i][v] = 1
// 然后从path[N][V]倒推出选中的商品
public static void main(String[] args) {
// 读取数据
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
for (int i = 0; i < N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
// 01背包
int[][] dp = new int[N + 1][V + 1];
int[][] path = new int[N + 1][V + 1];
// dp[0][0...V] 默认为0
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i] && dp[i - 1][j - v[i]] + w[i] > dp[i][j]) {
dp[i][j] = dp[i - 1][j - v[i]] + w[i];
// 物品被选中，path[i][j] = 1
path[i][j] = 1;
}
}
}
// 打印被选中物品的下标
for (int i = N, j = V; i > 0 && j > 0; i--) {
if (path[i][j] == 1) {
System.out.println(i+"号物品被选中");
j -= v[i];
}
}
}
空间复杂度优化（优化部分其实和具体题目关系不大了，完全是代码的优化）
; 时间复杂度O(V*N)以及确定了。空间复杂度，之前使用的是二维数组，可以降维到一维数组
转移方程：f(i,v) = max( f( i-1 , v ) , f( i-1，v-vi ) + wi )，可以观察到f(i,v)只和上一行有关
每一次循环，我们总是用新的一行去记录当前最大价值，实际上我们用到的只是上一行的值，那完全可以用dp[2][V]去代替之前的dp[N][V]。（即滚动数组）
如果用一维数组能否实现记录每次循环的最大价值呢，即dp[i][j]行记录的内容由dp[j]得到
image.png
看之前的代码
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i-1][j]; // 使用一维数组后，这行可以去掉，当前遍历，数组中存的就是上一行的数据
if (j >= v[i]) { // 当j < v[i]的时候，条件不成立，for循环可以改成j从v[i]开始，j -> v[i] ... V
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]); // dp[i][j]依赖于dp[i-1][j-v[i]]，如果j从0...V的话，j
// 后面的值可能会得到dp[i][j-v[i]]，因此j要从V...0
}
}
}
转移方程：dp[j] = max(dp[j],dp[j-vi]+w[j])
for (int i = 1; i <= N; i++) {
for (int j = V; j >=v[i]; j--) {
if (j >= v[i]) {
dp[j] = Math.max( dp[j],dp[ j - v[i] ] + w[i] );
}
}
}
leetcode题目
leetcode416题 分割等和子集
题目描述：
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
求解思路：
将数组分为两个子集，即选择一些数字组成一个集合，未选择的就是另一个集合
dp[i][j] 表示前i个数中选出一些，和正好等于j。dp[i][j]为boolean类型
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]
代码实现：
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int N = nums.length;
int sum = 0;
for (int i : nums) {
sum += i;
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
boolean[][] dp = new boolean[N][target + 1];
if (nums[0] <= target) {
dp[0][nums[0]] = true;
}
for (int i = 1; i < N; i++) {
for (int j = 0; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (nums[i] <= j) {
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i]];
}
}
}
return dp[N - 1][target];
}
空间优化
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int N = nums.length;
int sum = 0;
for (int i : nums) {
sum += i;
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
if (nums[0] <= target) {
dp[nums[0]] = true;
}
for (int i = 1; i < N; i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[target];
}
leetcode494题 目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个
整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
注意:
数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
leetcode1049题 最后一块石头的重量 II
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-stone-weight-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
