当前位置：首页 > news >正文

0/1背包与完全背包差异分析

news 2025/4/29 8:04:29

文章目录

定义差异分析
代码实现分析
总结

定义差异分析

0/1背包问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
完全背包问题：有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，价值是value[i] 。每件物品可以放入背包多次，求解将哪些物品装入背包里物品价值总和最大。

对于每一件物品，0/1背包问题是放和不放的问题，完全背包是，放多少件的问题（可以是0）

代码实现分析

为了易于理解，这里的代码没有使用滚动数组（dp数组压缩成一维）

/*** 0/1背包问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，价值是value[i] 。*      每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。* @param weights weight[i]第i件物品的重量* @param values value[i]第i件物品的价值* @param n 物品数量* @param w 背包容量* @return 最大价值*/
int zeroOneBackpack(int weights[], int values[], int n, int w) {// 1. dp[i][j] 从前i中材料中任选，装满容量为j的背包，最大的价值int dp[][] = new int[n][w + 1];/*2. 递推公式 根据是否放入物品i分两种情况1）不放入物品i，那么dp[i][j] = dp[i - 1][j]也就是从前i - 1中材料中任选，装满容量为j的背包，最大的价值2）放入物品i，那么dp[i][j] = values[i] + dp[i - 1][j - weights[i]]也就是放入物品i后，剩余的空间为j - weights[i]从i - 1中材料中任选，装满容量为j - weights[i]的背包，最大的价值为dp[i - 1][j - weights[i]]dp[i][j]为两个之和，即values[i] + dp[i - 1][j - weights[i]]3）如果容量j小于物品i的重量weight[i],那么就不需要考虑第二种情况dp[i][j] = dp[i - 1][j];if (j >= weights[i])dp[i][j] = max(dp[i][j], values[i] + dp[i - 1][j - weights[i]])*/// 3. 初始化for (int j = weights[0]; j <= n; j ++) {dp[0][j] = values[0];}// 4. 递推顺序for (int i = 1; i < n; i ++) {for (int j = 1; j <= n; j ++) {dp[i][j] = dp[i - 1][j];if (j >= weights[i]) {dp[i][j] = max(dp[i][j], values[i] + dp[i - 1][j - weights[i]]);}}}return dp[n - 1][w];
}

/*** 完全背包问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，价值是value[i] 。*      每件物品可以选多次（包含0），求解将哪些物品装入背包里物品价值总和最大。* @param weights weight[i]第i件物品的重量* @param values value[i]第i件物品的价值* @param n 物品数量* @param w 背包容量* @return 最大价值*/
int completeBackpack(int weights[], int values[], int n, int w) {// 1. dp[i][j] 从物品0-i中任取，每个物品能取无限次//    装满容量为j的背包，能获取的最大价值int dp[][] = new int[n][w + 1];/*2. 递推公式 根据是否放入物品i分两种情况1）不放入物品i，那么dp[i][j] = dp[i - 1][j]也就是从前i - 1中材料中任选，装满容量为j的背包，最大的价值2）放入物品i，那么dp[i][j] = values[i] + dp[i - 1][j - weights[i]]也就是放入物品i后，剩余的空间为j - weights[i]再从i中材料中任选，装满容量为j - weights[i]的背包，最大的价值为dp[i][j - weights[i]]dp[i][j]为两个之和，即values[i] + dp[i][j - weights[i]]3）如果容量j小于物品i的重量weight[i],那么就不需要考虑第二种情况dp[i][j] = dp[i - 1][j];if (j >= weights[i])dp[i][j] = max(dp[i][j], values[i] + dp[i][j - weights[i]])*/// 3. 初始化for (int j = 0; j <= w; j ++) {// 背包能放多少个物品0 (j / weights[0])dp[0][j] = (j / weights[0]) * values[0];}// 4. 递归顺序for (int i = 1; i < n; i++) {for (int j = 0; j <= w; j++) {dp[i][j] = dp[i - 1][j];if (j >= weights[i]) {// dp[i][j] = max(dp[i][j], values[i] + dp[i - 1][j - weights[i]]);// 上一行注释是0/1背包的递推公式// 0/1背包是values[i] + dp[i - 1][j - weights[i]]// 完全背包是values[i] + dp[i][j - weights[i]]// 0/1背包，如果我放入物品i，剩余的容量为j - weights[i]//		因为物品i已经放入了，那么我需要找的是从物品0 ~ i-1中任选，能获取的最大价值//		所以是dp[i - 1][j - weights[i]]// 完全背包，如果我放入物品i，剩余的容量为j - weights[i]//		此时放入了物品i，但因为每一件物品可以放入多次，那么我需要找的是，//		从物品0 ~ i中任选，能获取的最大价值，也就是dp[i][j - weights[i]]// 综上，0/1背包与完全背包在于我放入物品i后，剩余的容量能放的物品分别为[0, i-1]和[0, i]dp[i][j] = max(dp[i][j], values[i] + dp[i][j - weights[i]]);}}}return dp[n - 1][w];
}