0-1背包问题（动态规划）

0-1背包

问题描述：有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v，共有M个物品。

解：定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。那么结果为dp[M][N]就是原问题的解。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，dp[i][j] = dp[i-1][j]。 第 i 件物品添加到背包中，dp[i][j] = dp[i-1][j-w[i]] + v。第i件物品添加到背包并且体积不超过j，那么前i-1件物品的体积不超过j-w[i]（减去第i件物品的体积）。 第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为： dp[i][j] = max (dp[i-1][j], dp[i-1][j-w[i]] + v)

/* N 为背包总体积 * M 为物品数量 * weights 数组存储 N 个物品的重量 * values 数组存储 N 个物品的价值 */ public int bag(int N, int M, int[] weights, int[] values) { int[][] dp = new int[M + 1][N + 1]; for (int i = 1; i <= M; i++) { int w = weights[i - 1], v = values[i - 1]; for (int j = 1; j <= N; j++) { if (j >= w) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[M][N]; }

为什么不能用贪心

0-1 背包问题无法使用贪心算法来求解，也就是说不能按照先添加性价比最高的物品来达到最优，这是因为这种方式可能造成背包空间的浪费，从而无法达到最优。考虑下面的物品和一个容量为 5 的背包，如果先添加物品 0 再添加物品 1，那么只能存放的价值为 16，浪费了大小为 2 的空间。最优的方式是存放物品 1 和物品 2，价值为 22.

idwvv/w01661210523124

变型

完全背包：物品数量为无限个

多重背包：物品数量有限制

多维费用背包：物品不仅有重量，还有体积，同时考虑这两种限制

其它：物品之间相互约束或者依赖

0-1背包变型题

题目：

题解：看成sum/2背包问题，背包容量为数组和的一半。 dp[i][j] = true 表示加到第i件物品时，容量为j的背包满了，不满则为false. 认为j=0时是满的 。

那么dp[i][j]，第i个物品时容量为j是满的，可能是i-1就满了(dp[i-1][j])，也可能是加上第i个之后满了dp[i-1][j-w] + v。

代码

package leetcode.dp; import java.util.Scanner; /* * 416: 分割等和子集 */ public class CanPartition { public static void main(String[] args) { Scanner s = new Scanner(System.in); while(s.hasNext()) { int n = s.nextInt(); int[] a = new int[n]; for(int i=0;i<n;i++) { a[i] = s.nextInt(); } System.out.println(canPartition(a)); } s.close(); } public static boolean canPartition(int[] nums) { if(nums == null || nums.length == 0) return true; //空的时候分两个空的 int sum = 0; for(int i=0;i<nums.length;i++) { sum+=nums[i]; } if(sum%2 != 0) return false; //boolean dp[i][j]= true 代表 i个物品放到容量为j的背包里，刚好放满。j = sum/2; boolean[][] dp = new boolean[nums.length + 1][sum/2+1]; for(int j=1;j<=sum/2;j++) { dp[0][j] = false; //背包>=1, 不放物品, 即放不满 } for(int i=0;i<=nums.length;i++) { dp[i][0] = true; //背包容量=0，默认是能放满 } for(int i=1;i<=nums.length;i++) { for(int j=1;j<=sum/2;j++) { int v = nums[i-1]; if(j<v) { dp[i][j] = dp[i-1][j]; }else { dp[i][j] = dp[i-1][j-v] || dp[i-1][j]; } } } return dp[nums.length][sum/2]; } }