一、题目
给定 n 个物品,第 i 个物品的重量为 wgt[i-1]、价值为 val[i-1] ,和一个容量为 cap 的背包。每个物品可以重复选取,问在限定背包容量下能放入物品的最大价值。
二、和ChatGPT聊聊
您
您是一位资深算法工程师,请深入浅出地给出完全背包问题的分析过程和完整带注释的Java代码实现
GPT-4-Turbo
完全背包问题是动态规划中的一个经典问题,与0-1背包问题相似,但在完全背包问题中,每种物品可以被无限次选取。这个问题的目标是在不超过背包容量的前提下,最大化背包中物品的总价值分析过程
定义状态:定义
dp[i][c]
为考虑前i
个物品,当背包容量为c
时能达到的最大价值。状态转移方程:dp[i][c] = max(dp[i-1][c], dp[i][c-wgt[i-1]] + val[i-1])
- 如果不选当前物品
i
,则dp[i][c] = dp[i-1][c]
,直接继承前一个状态的值。- 如果选当前物品
i
,则dp[i][c] = dp[i][c-wgt[i]] + val[i]
,表示在当前背包容量减去物品i
的重量后的最大价值基础上加上物品i
的价值。由于物品可以被无限次选取,我们仍然在考虑物品i
。初始化:
dp[0][...] = 0
,表示当没有物品可选时,任何容量的背包的最大价值都是0。目标:
dp[n][cap]
,表示考虑所有n
个物品,当背包容量为cap
时能达到的最大价值。
您
那为什么转移方程不是 dp[i][c] = max(dp[i-1][c], max(dp[i-1][c-wgt[i-1]] + val[i-1],dp[i][c-wgt[i-1]] + val[i-1]))
GPT-4-Turbo
您提出的状态转移方程: [dp[i][c] = max(dp[i-1][c], max(dp[i-1][c-wgt[i-1]] + val[i-1], dp[i][c-wgt[i-1]] + val[i-1]))]
实际上包含了冗余的比较。这是因为,当我们在解决完全背包问题时,对于每个物品,我们有两个选择:不选这个物品,或者选这个物品。如果选择不选这个物品,我们就直接继承了前一个状态的值,即
dp[i-1][c]
。如果选择选这个物品,我们需要考虑的是在当前物品可以被无限选取的情况下,选择这个物品后的最优解,即dp[i][c-wgt[i-1]] + val[i-1]
。在这里,
dp[i][c-wgt[i-1]] + val[i-1]
已经隐含了dp[i-1][c-wgt[i-1]] + val[i-1]
的情况。这是因为dp[i][c-wgt[i-1]]
已经考虑了所有包括第 i 个物品在内的选择,这自然包括了从不选择第 i 个物品到选择多次第 i 个物品的所有情况。因此,dp[i][c-wgt[i-1]] + val[i-1]
实际上已经覆盖了dp[i-1][c-wgt[i-1]] + val[i-1]
的情况,使得后者成为前者的一个子情况。因此,原始的状态转移方程: [dp[i][c] = \max(dp[i-1][c], dp[i][c-wgt[i-1]] + val[i-1])]
已经足够覆盖所有情况,无需再进行冗余的比较。这个方程简洁地表达了完全背包问题的核心思想:对于每个物品,我们可以选择不选它,或者在选它的情况下,考虑包括它自身在内的所有可能性。
三、GPT-4-Turbod的java实现
1 public class CompleteKnapsack { 2 3 /** 4 * 解决完全背包问题的函数 5 * @param wgt 物品重量数组 6 * @param val 物品价值数组 7 * @param cap 背包容量 8 * @return 背包能装入物品的最大价值 9 */ 10 public static int completeKnapsack(int[] wgt, int[] val, int cap) { 11 int n = wgt.length; // 物品的数量 12 int[][] dp = new int[n + 1][cap + 1]; // dp数组,多出的一行一列是为了方便处理边界情况 13 14 // 初始化dp数组,Java默认初始化为0,所以这里可以省略 15 16 // 遍历所有物品 17 for (int i = 1; i <= n; i++) { 18 // 遍历所有可能的背包容量 19 for (int c = 0; c <= cap; c++) { 20 // 不选当前物品i 21 dp[i][c] = dp[i - 1][c]; 22 // 选当前物品i,前提是背包容量足够 23 if (c >= wgt[i - 1]) { 24 dp[i][c] = Math.max(dp[i][c], dp[i][c - wgt[i - 1]] + val[i - 1]); 25 } 26 } 27 } 28 29 // 返回考虑所有物品,背包容量为cap时的最大价值 30 return dp[n][cap]; 31 } 32 33 public static void main(String[] args) { 34 int[] wgt = {1, 3, 4}; // 物品重量 35 int[] val = {15, 20, 30}; // 物品价值 36 int cap = 4; // 背包容量 37 38 System.out.println("最大价值: " + completeKnapsack(wgt, val, cap)); 39 } 40 }View Code
标签:背包,val,int,wgt,算法,物品,ChatGPT,dp From: https://www.cnblogs.com/newhope/p/18187969