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

算法学习笔记(8.4)-完全背包问题

目录

Question:

图例:

动态规划思路

2 代码实现:

3 空间优化:

代码实现:

下面是0-1背包和完全背包具体的例题:

代码实现:

图例:

空间优化代码示例

Question

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

图例:

  1. 动态规划思路

完全背包问题和0-1背包问题非常相似,区别仅在于不限制物品的选择次数。

  1. 在0-1背包问题中,每种物品只有一个,因此将物品i放入到被曝后,只能从前i-1个物品选择。
  2. 在完全背包问题中,每种物品的数量都是无限的,因此将物品i放入到背包后,仍可以从前i个物品中选择。

在完全背包问题的规定下,状态[i,c]的变化分为以下两种情况。

  1. 不放入物品i:与0-1背包问题相同转移至[i-1,c]。
  2. 放入物品i:与0-1背包问题不同,转移至[i,c-wgt[i-1]]。

从而转移状态方程为:

dp[i,c] = max(dp[i-1,c],dp[i,c-wgt[i-1]]+val[i-1])

2 代码实现:
# python 代码示例
def unbound_knap_sack_dp(wgt, val, cap) :n = len(wgt)dp = [ [0] * (cap + 1) for _ in range(n + 1)]for i in range(1, n + 1) :for j in range(1, cap + 1) :if wgt[i - 1] > c :dp[i][c] = dp[i - 1][c]else :dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]]  + val[i - 1])return dp[n][cap]
// c++ 代码示例int unboundKnapSackDP(vector<int> &wgt, vector<int> &val, int cap)
{int n = wgt.size() ;vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0)) ;for (int i = 1 ; i <= n ; i++){for (int j = 1 ; j <= cap ; j++){if (wgt[i - 1] > c){dp[i][c] = dp[i - 1][c] ;}else{dp[i][c] = max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1) ;}}}return dp[n][cap] ;
}

3 空间优化:

由于当前状态是从左边和上边的状态转移而来,因此空间优化后应该对dp表中的每一行进行正序遍历。

图例所示:

代码实现:
# python 代码示例def unbound_knap_sack_dp_comp(wgt, val, cap) :n = len(wgt)dp = [0] * (cap + 1)for i in range(1, n + 1) :for j in range(1, cap + 1) :if wgt[i - 1] > c :dp[c] = dp[c]else :dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]) return dp[cap] ;
// c++ 代码示例int unboundKnapSackDPComp(vector<int> &wgt, vector<int> &val, int cap)
{int n = wgt.size() ;vector<int> dp(cap + 1, 0) ;for (int i = 1 ; i <= n ; i ++){for (int j = 1 ; j <= cap ; j++){if (wgt[i - 1] > c){dp[c] = dp[c] ;}else{dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]) ;}}}return dp[c] ;
}

下面是0-1背包和完全背包具体的例题:

零钱兑换问题:给定n中硬币,第i种硬币的面值为coins[i-1],目标金额为amt,每种硬币可以重复选取,问能够凑出目标金额的最少硬币数。如果无法凑出目标金额,则返回-1。

图例:

动态规划的思路:

零钱兑换可以看作是完全背包的一种特殊情况,两者具有以下联系和不同点。

  1. 两道题目可以相互转化,“物品“对应”硬币“、”物品重量“对应”硬币面值“、”背包容量“对应”目标金额“。
  2. 优化目标相反,完全背包问题是要最大化物品价值,零钱兑换问题是要最小化硬币数量。
  3. 完全背包问题是求“不超过“背包容量下的解,零钱兑换是求”恰好“凑到目标金额的解。

第一步:思考每轮的决策,定义状态,从而得到dp表

状态[i,a]对应的子问题为:前i种硬币能够凑出金额a的最少硬币数量,记作dp[i,a]。

二维dp表的尺寸为(n+1)*(amt+1).

第二步:找出最优子结构,进而推导出状态转移方程

本题与完全背包问题的转移状态方程存在以下两点差异。

  1. 本题要求最小值,因此需将运算符max()更改为min()。
  2. 优化主体是硬币数量而非商品的价值,因此在选中硬币时需执行+1即可。

dp[i,a] = min(dp[i-1,a],dp[i,a-coins[i-1]]+1)

第三步:确定边界和状态转移顺序

当目标金额为0时,凑出它的最小硬币数量为0,即首列所有dp[i,0]都等于0。

当无硬币时,无法凑出任意>0的目标金额,即使无效解。为使状态转移方程中的min()函数能够识别并过滤无效解,我们使用+∞来表示他们,即令首行所有dp[0,a]都等于+∞。

代码实现:
def coin_change_dp(coins, amt) :n = len(coins)dp = [ [0] * (amt + 1) for _ in range(n + 1)]for j in range(1, amt + 1) :dp[0][j] = inffor i in range(1, n + 1) :dp[i][0] = 0for i in range(1, n + 1) :for j in range(1, cap + 1) :if coins[i - 1] > j :dp[i][j] = dp[i - 1][j]else :dp[i][j] = max(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)return dp[n][amt] if dp[n][amt] != inf else -1
int coinsChangeDP(vector<int> &coins, int amt)
{int n = coins.size() ;vector<vector<int>> dp(n + 1, vector<int>(amt + 1, 0)) ;for (int j = 1 ; j <= amt ; j++) {dp[0][j] = INT_MAX ;}for (int i = 1 ; i <= n ; i++){dp[i][0] = 0 ;}for (int i = 1 ; i <= n ; i++){for (int j = 1 ; j <= amt ; j++){if (coins[i - 1] > j){dp[i][j] = dp[i - 1][j] ;}else{dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1) ;}}}return dp[n][amt] != INT_MAX ? dp[n][amt] : -1 ;}

图例:

空间优化代码示例:
# python 代码示例def coins_change_dp_comp(coins, amt) :n = len(coins)dp = [inf] * (amt + 1)for i in range(1, n + 1) :for j in range(1, cap + 1) :if (coins[i - 1] > j) :dp[j] = dp[j]else :dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1)return dp[amt] if dp[amt] != inf else -1
// c++ 代码示例
int coinsChangeDPComp(vector<int> &coins, int amt)
{int n = coins.size() ;vector<int> dp(cap + 1, INT_MAX) ;for (int i = 1 ; i <= n ; i++){for (int j = 1 ; j <= amt ; j++){if (coins[i - 1] > j){dp[j] = dp[j] ;}else{dp[j] = min([j], [j - coins[i - 1]] + 1) ;}}}return dp[amt] != INT_MAX ? dp[amt] : -1 ;}

相关文章:

算法学习笔记(8.4)-完全背包问题

目录 Question&#xff1a; 图例&#xff1a; 动态规划思路 2 代码实现&#xff1a; 3 空间优化&#xff1a; 代码实现&#xff1a; 下面是0-1背包和完全背包具体的例题&#xff1a; 代码实现&#xff1a; 图例&#xff1a; 空间优化代码示例 Question&#xff1a; 给定n个物品…...

C++catch (...)陈述

catch (...)陈述 例外处理可以有多个catch&#xff0c;如果catch后的小括弧里面放...&#xff0c;就表示不限型态种类的任何例外。 举例如下 #include <iostream>int main() {int i -1;try {if (i > 0) {throw 0;}throw 2.0;}catch (const int e) {std::cout <…...

Redis实践

Redis实践 使用复杂度高的命令 如果在使用Redis时&#xff0c;发现访问延迟突然增大&#xff0c;如何进行排查&#xff1f; 首先&#xff0c;第一步&#xff0c;建议你去查看一下Redis的慢日志。Redis提供了慢日志命令的统计功能&#xff0c;我们通过以下设置&#xff0c;就…...

【Lora模型推荐】Stable Diffusion创作具有玉石翡翠质感的图标设计

站长素材AI教程是站长之家旗下AI绘图教程平台 海量AI免费教程&#xff0c;每日更新干货内容 想要深入学习更多AI绘图教程&#xff0c;请访问站长素材AI教程网&#xff1a; AI教程_深度学习入门指南 - 站长素材 (chinaz.com) logo版权归各公司所有&#xff01;本笔记仅供AIGC…...

vscode 远程开发

目录 vscode 远程连接 选择 Python 环境 vscode 远程连接 按 CtrlShiftP 打开命令面板。输入并选择 Remote-SSH: Open SSH Configuration File...。选择 ~/.ssh/config 文件&#xff08;如果有多个选项&#xff09;。在打开的文件中添加或修改你的 SSH 配置。 这个可以右键…...

前端Vue组件化实践:打造灵活可维护的地址管理组件

随着前端技术的不断演进&#xff0c;复杂度和开发难度也随之上升。传统的一体化开发模式使得每次小小的修改或功能增加都可能牵一发而动全身&#xff0c;严重影响了开发效率和维护成本。组件化开发作为一种解决方案&#xff0c;通过模块化、独立化的开发方式&#xff0c;实现了…...

虚幻引擎ue5游戏运行界面白茫茫一片,怎么处理

根剧下图顺序即可调节游戏运行界面光照问题&#xff1a; 在大纲里找到post&#xff0c;然后选中它&#xff0c;找到Exposure 把最低亮度和最高亮度的0改为1即可...

《代理选择与反爬虫策略探究:如何优化网络爬虫效率与稳定性》

代理IP如何选以及常见反爬策略 为什么需要代理&#xff1f; 因为有的网站会封IP&#xff0c;用户如果没有登录&#xff0c;那IP就是身份标识&#xff0c;如果网站发现用户行为异常就非常可能封IP 什么是代理IP 就是让一个人帮你转交请求&#xff0c;帮你转交的人对面不熟&a…...

Kotlin Flow 防抖 节流

防抖和节流是针对响应跟不上触发频率这类问题的两种解决方案。 一:防抖&#xff08;debounce&#xff09;的概念&#xff1a; 防抖是指当持续触发事件时&#xff0c;一定时间段内没有再触发事件&#xff0c;事件处理函数才会执行一次&#xff0c; 如果设定时间到来之前&#x…...

Android Studio下载与安装

Android Studio下载与安装_android studio下载安装-CSDN博客...

【LC刷题】DAY24:122 55 45 1005

122. 买卖股票的最佳时机 II class Solution { public:int maxProfit(vector<int>& prices) {int result 0;for(int i 1; i < prices.size(); i ){result max(prices[i] - prices[ i - 1], 0);}return result;} };55. 跳跃游戏 link class Solution { public…...

从零开始的python学习生活2

接上封装 class Phone:__volt0.5def __keepsinglecore(self):print("让cpu以单核运行")def if5G(self):if self.__volt>1:print("5G通话已开启")else:self.__keepsinglecore()print("电量不足&#xff0c;无法使用5G通话&#xff0c;已经设置为单…...

【并发编程】进程 线程 协程

进程&#xff08;Process&#xff09;、线程&#xff08;Thread&#xff09;和协程&#xff08;Coroutine&#xff09;构成了计算机科学中实现任务并发执行的三种核心抽象机制。通常&#xff0c;为了提高程序的执行效率&#xff0c;开发者会根据应用场景和性能需求&#xff0c;…...

Vue的生命周期函数有哪些?详细说明

Vue.js 的生命周期函数包括以下几个阶段&#xff0c;每个阶段都有相应的钩子函数可以用来在特定时机执行自定义的逻辑。这些生命周期钩子函数使得我们可以在组件的不同阶段进行操作&#xff0c;从而管理组件的状态和行为。 1. beforeCreate&#xff1a; - 描述&#xff1a;…...

大语言模型应用--AI工程化落地

文章目录 大语言模型概述什么是大语言模型什么是机器学习什么是深度学习 理解大语言模型历史沿革关键 AIGC系统AI工程化项目的落地落地的方法Prompt工程&#xff08;第一阶段&#xff09;RAG检索&#xff08;第二阶段&#xff09;训练特定功能模型&#xff08;第三阶段&#xf…...

我会什么开发技能

java我会什么&#xff1f; 一、并发编程 1、并发编程&#xff1a;jdk中的courren包只能够类实现&#xff08;seamplore&#xff0c;CountDownLaunch&#xff0c;Pharse&#xff0c;CycliBarrier&#xff0c;CompletableFuture&#xff09;&#xff0c;AQS的原理&#xff0c;线…...

Run LoongArch64 Alpine VM on x86_64

一、Build from source(build on x86_64) Obtain the latest libvirt, virt-manager, and qemu source code, compile and install them. 1.1 Build libvirt from source sudo apt-get update sudo apt-get install augeas-tools bash-completion debhelper-compat dh-apparm…...

4层负载均衡和7层负载均衡

四层负载均衡&#xff08;Layer 4 Load Balancing&#xff09;指的是在网络传输层&#xff08;TCP/IP模型中的第四层&#xff09;进行负载均衡的技术。四层负载均衡通常使用IP地址、端口号和协议等信息来将网络流量分配到多个服务器上。它主要关心网络层的信息&#xff0c;不涉…...

前端Vue组件化实践:打造仿京东天猫商品属性选择器组件

在前端开发领域&#xff0c;随着业务需求的日益复杂和技术的不断进步&#xff0c;传统的整体式应用开发模式已逐渐显得捉襟见肘。面对日益庞大的系统&#xff0c;每次微小的功能修改或增加都可能导致整个逻辑结构的重构&#xff0c;形成牵一发而动全身的困境。为了解决这一问题…...

智慧城市3d数据可视化系统提升信息汇报的时效和精准度

在信息大爆炸的时代&#xff0c;数据的力量无可估量。而如何将这些数据以直观、高效的方式呈现出来&#xff0c;成为了一个亟待解决的问题。为此&#xff0c;我们推出了全新的3D可视化数据大屏系统&#xff0c;让数据“跃然屏上”&#xff0c;助力您洞察先机&#xff0c;决胜千…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...