韩国时尚网站欣赏,青海网站设计高端,赣州朝扬网络科技有限公司,燕郊做网站的引言
背包问题是计算机科学领域的一个经典优化问题#xff0c;分为多种类型#xff0c;其中最常见的是0-1背包问题和完全背包问题。这两种问题的核心在于如何在有限的空间内最大化收益#xff0c;但它们之间存在一些关键的区别#xff1a;0-1背包问题允许每个物品只能选择…引言
背包问题是计算机科学领域的一个经典优化问题分为多种类型其中最常见的是0-1背包问题和完全背包问题。这两种问题的核心在于如何在有限的空间内最大化收益但它们之间存在一些关键的区别0-1背包问题允许每个物品只能选择一次而完全背包问题则允许无限次选取同一物品。本篇博客将分别介绍这两个问题的动态规划解法并附带相应的Java代码实现。
0-1背包问题
问题描述
假设你有一个背包其最大承重能力为W千克现在有一系列物品每个物品有自己的重量Wi和价值Vi。你的任务是从这些物品中挑选一部分装入背包使得背包的价值尽可能大但不能超过背包的最大承重限制。
解决方案
我们可以采用动态规划的方法来求解这个问题。定义一个二维数组dp[i][j]表示从前i个物品中选择若干个放入容量为j的背包所能获得的最大价值。状态转移方程 Java代码实现
package dp;import java.util.ArrayList;
import java.util.List;public class Knapsack {public static void main(String[] args) {int n 4; // 物品数量int bagweight 16; // 背包最大容量int[] weight {5, 7, 3, 4}; // 物品重量int[] value {2, 5, 8, 1}; // 物品价值// 初始化 dp 数组int[][] dp new int[n 1][bagweight 1];// 动态规划填充 dp 数组for (int i 1; i n; i) {for (int j 0; j bagweight; j) {if (j weight[i - 1]) {dp[i][j] dp[i - 1][j]; // 不选择当前物品} else {dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] value[i - 1]); // 选择或不选择当前物品}}}// 输出最大价值System.out.println(最大价值: dp[n][bagweight]);// 回溯找到具体的物品ListInteger selectedItems new ArrayList();int i n, j bagweight;while (i 0 j 0) {if (dp[i][j] ! dp[i - 1][j]) {selectedItems.add(i - 1); // 物品索引从0开始j - weight[i - 1];}i--;}// 输出选择的物品System.out.print(选择的物品: );for (int item : selectedItems) {System.out.print(item (重量: weight[item] , 价值: value[item] ) );}System.out.println();}
} 完全背包问题
问题描述
完全背包问题与0-1背包问题类似不同之处在于每个物品的数量不限即你可以无限制地选择同一个物品。
解决方案
对于完全背包问题我们需要稍微修改一下状态转移方程。由于每个物品都可以多次选择因此需要在循环中考虑是否要加入该物品到背包中。 状态表示 dp[i][j] 表示前 i 种物品放入容量为 j 的背包里任意取的最大价值。 确定边界和遍历顺序 先遍历背包重量 (内层)再遍历物品 (外层循环)。 for(int i1;in;i) // 物品数量for(int j1;jm;j) // 背包容量if(jw[i]) // 判断是否能放得下第i件物品dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]v[i]); // 更新dp数组else dp[i][j]dp[i-1][j]; // 不选第i件物品 找到状态转移方程 状态转移方程是关键部分它描述了如何从已知的状态推导出新的状态。 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 这意味着对于每一件物品可以选择放进去或者不放比较两种情况下所能获得的最大价值。 Java代码实现
package dp;import java.util.ArrayList;
import java.util.List;public class AllPack {public static void main(String[] args) {int n 3; // 物品数量int bagweight 7; // 背包最大容量int[] weight {3, 4, 2}; // 物品重量int[] value {4, 5, 3}; // 物品价值// 初始化 dp 数组int[][] dp new int[n 1][bagweight 1];// 动态规划填充 dp 数组for (int i 1; i n; i) {for (int j 0; j bagweight; j) {dp[i][j] dp[i - 1][j]; // 不选择当前物品if (j weight[i - 1]) {dp[i][j] Math.max(dp[i][j], dp[i][j - weight[i - 1]] value[i - 1]); // 选择或不选择当前物品}}}// 输出最大价值System.out.println(最大价值: dp[n][bagweight]);// 回溯找到具体的物品ListInteger selectedItems new ArrayList();int i n, j bagweight;while (i 0 j 0) {if (j weight[i - 1] dp[i][j] ! dp[i - 1][j]) {selectedItems.add(i - 1); // 物品索引从0开始j - weight[i - 1];}i--;}// 输出选择的物品System.out.print(选择的物品: );for (int item : selectedItems) {System.out.print(item (重量: weight[item] , 价值: value[item] ) );}System.out.println();}
} 0-1背包问题 每个物品只能选择一次。回溯逻辑中一旦确定选择了某个物品就从当前的背包容量中减去该物品的重量并且继续回溯下一个物品。 完全背包问题 每个物品可以选择多次直到背包容量不允许为止。回溯逻辑中需要检查在当前背包容量下可以选择该物品的次数。这通常涉及到一个循环直到背包容量不足以再添加一个该物品为止。
