首页 > 编程语言 >跟着ChatGPT学算法-完全背包问题

跟着ChatGPT学算法-完全背包问题

时间:2024-05-12 17:31:05浏览次数:27  
标签:背包 val int wgt 算法 物品 ChatGPT dp

一、题目

给定 n 个物品,第 i 个物品的重量为 wgt[i-1]、价值为 val[i-1] ,和一个容量为 cap 的背包。每个物品可以重复选取,问在限定背包容量下能放入物品的最大价值。

 

二、和ChatGPT聊聊

您是一位资深算法工程师,请深入浅出地给出完全背包问题的分析过程和完整带注释的Java代码实现

 

GPT-4-Turbo

 完全背包问题是动态规划中的一个经典问题,与0-1背包问题相似,但在完全背包问题中,每种物品可以被无限次选取。这个问题的目标是在不超过背包容量的前提下,最大化背包中物品的总价值  

分析过程

  1. 定义状态:定义 dp[i][c] 为考虑前 i 个物品,当背包容量为 c 时能达到的最大价值。

  2. 状态转移方程: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
  3. 初始化:dp[0][...] = 0,表示当没有物品可选时,任何容量的背包的最大价值都是0。

  4. 目标: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

相关文章

  • py面向算法
    近期想系统性的学习学习python,我想着了解一门语言是不是最开始就要会用他的一些基本语法来写题呢,抱着这个想法我就开始用c++写完一道题后用py再写一遍.但是py主要的一些语法还好,只是表现形式不同而已,但是py的输入输出和数组方面相对来说特殊不少,或者根本就没有数组这个概念,......
  • 策略梯度玩 cartpole 游戏,强化学习代替PID算法控制平衡杆
     cartpole游戏,车上顶着一个自由摆动的杆子,实现杆子的平衡,杆子每次倒向一端车就开始移动让杆子保持动态直立的状态,策略函数使用一个两层的简单神经网络,输入状态有4个,车位置,车速度,杆角度,杆速度,输出action为左移动或右移动,输入状态发现至少要给3个才能稳定一会儿,给2个完全学不明白,......
  • 记字符串匹配KMP算法
    字符串匹配是一类经典的问题,在字符串s中找出模式串t第一个元素的下标,如果没有匹配到,则返回-1。此问题在leetcode中甚至归类为简单。解决此问题最直接的思路是使用暴力解法,从第0个元素开始逐个比较元素,当字符不匹配时,s的指针向前移动一位,不断重复。这种思路最简单且直接,但是无法通......
  • 自定义各类基础排序算法
    接口函数基础信息/********************************************************************* 文件名称: 数据结构中对于无序数列的排序算法* 文件作者:[email protected]* 创建日期:2024/05/11* 文件功能:对无序数列进行排序* 注意事项:None** C......
  • 匈牙利算法模板(二分图)
    booldfs(intnow){for(inti=h[now];i;i=nxt[i]){intt=to[i];//这里不用考虑会有回到父结点的边的问题//因为每次都是从左部找邻接点if(!vis[t]){vis[t]=true;//如果邻接点t是非匹配点,则找到一条增广路,匹配......
  • 代码随想录算法训练营第四天 | 23.两l两交换链表中的节点 19.删除链表的倒数第N个节点
    23.两两交换链表中的两个节点题目链接文章讲解视频讲解时间复杂度o(n)空间复杂度o(1)tips:画图,并将每一步操作用伪代码写出来,然后将代码理顺可以避免修改代码的麻烦初始化的时候就要将previous初始化为current的前一个节点,这样可以保证循环的第一步满足循环要求cla......
  • 代码随想录算法训练营第第二天 | 24. 两两交换链表中的节点 、19.删除链表的倒数第N
    两两交换链表中的节点用虚拟头结点,这样会方便很多。本题链表操作就比较复杂了,建议大家先看视频,视频里我讲解了注意事项,为什么需要temp保存临时节点。题目链接/文章讲解/视频讲解:https://programmercarl.com/0024.两两交换链表中的节点.html/***Definitionforsingly-li......
  • 读天才与算法:人脑与AI的数学思维笔记25_涌现理论
    1. 人工智能新闻1.1. 人工智能新闻报道算法的核心是如何将未经处理的原始数据转换成新闻报道1.2. 很少有记者为美联社决定使用机器来帮助报道这些新闻持反对意见1.2.1. 像“Wordsmith”这样的算法,具有自动化的洞察力、科学的叙事能力,现在正被应用于基于大量数据的分析报道......
  • 算法之数学知识
    威尔逊定理:如果p是指数,那么(p-1)!对于p取模恒等于p-1.逆元的概念及其求解方法https://blog.csdn.net/weixin_40895249/article/details/124477029?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171394439916800188566032%2522%252C%2522scm%2522%253A%25222014071......
  • TheAlgorithms/C - 各种基础算法、数据结构的 C 语言实现+armink/SFUD - 一款基于 JED
    1、OpenMV-RT-基于恩智浦i.MXRT系列的开源机器视觉AI模块OpenMV-RT是一款基于恩智浦最近主打的i.MXRT超高性能系列MCU的视觉模块,模块设计者是恩智浦大牛工程师宋岩(对,就是ARMCortex-M3权威指南中文版作者)。模块源代码: https://github.com/RockySong/micropython......