动态规划11,完全背包模板

NC309 完全背包

在这里插入图片描述

问题一:求这个背包至多能装多大价值的物品?

  1. 状态表示:经验+题目要求
    dp[i][j] 表示 从前i个物品中挑选,总体积不超过j,所有选法中,能选出来的最大价值。

  2. 状态转移方程
    根据最后一步的状态:选还是不选,选的话选几个

这里有一个化简的过程

在这里插入图片描述

  1. 初始化
    i为0,表示从前0个物品选,当然全为0;
    j为0,表示从前i个物品选,总体积不超过0,也全为0;
    在这里插入图片描述

  2. 填表顺序
    从上往下填每一行
    每一行从左往右

在这里插入图片描述

问题二:若背包恰好装满,求至多能装多大价值的物品?

  1. 状态表示:经验+题目要求
    dp[i][j] 表示 从前i个物品中挑选,总体积正好等于j,所有选法中,能选出来的最大价值。

  2. 状态转移方程
    根据最后一步的状态:选还是不选,同时当无法体积为j的时候,就令值为-1;

如果不选:dp[i][j] = dp[i-1][ j ]; 不用考虑等不等于-1
如果选: dp[i][j] = w[i] + dp[ i ][ j - v[i] ]; 但同时需要注意 j-v[i] 的大小,不能为负数。
同时需要注意dp[i-1][ j - v[i] ]不为-1

  1. 初始化
    i为0,表示从前0个物品选,总体积正好等于 j ,除了0后面全为-1;
    j为0,表示从前i个物品选,总体积正好为0,也全为0;

在这里插入图片描述
4. 填表顺序
从上到下
在这里插入图片描述

vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {// write code herevector<vector<int>> dp(n+1,vector<int>(v+1));for(int i = 1; i <= n; i++){for(int j = 1; j<=v; j++){dp[i][j] = dp[i-1][j];if(j - nums[i-1][0] >= 0)dp[i][j] = max(dp[i-1][j],dp[i][j - nums[i-1][0]] + nums[i-1][1] );}}vector<int> ret;ret.push_back(dp[n][v]);for(int j = 1; j<=v; j++)dp[0][j] = -1;for(int i = 1; i <= n; i++){for(int j = 1; j<=v; j++){dp[i][j] = dp[i-1][j];if(j - nums[i-1][0] >= 0 && dp[i][j-nums[i-1][0]] != -1)dp[i][j] = max(dp[i-1][j],dp[i][j - nums[i-1][0]] + nums[i-1][1] );}}ret.push_back(dp[n][v] == -1 ? 0 : dp[n][v]);return ret;}

322. 零钱兑换

在这里插入图片描述

  1. 状态表示:经验+题目要求
    dp[i][j] 表示 从前i个硬币中挑选,总体积正好等于j,所有选法中,最少的硬币个数。

  2. 状态转移方程
    根据最后一步的状态:选还是不选。

同完美背包问题
在这里插入图片描述

  1. 初始化
    j为0不用管, 当i为0时为了不影响min判断,我们设大值0x3f3f3f3f;
    在这里插入图片描述
class Solution {
public:int coinChange(vector<int>& coins, int amount) {const int INF = 0x3f3f3f3f;int n = coins.size();vector<vector<int>> dp(n+1,vector<int>(amount+1));for(int j = 1; j<= amount; j++)dp[0][j] = INF;for(int i = 1; i <= n; i++){for(int j = 1; j<=amount; j++){dp[i][j] = dp[i-1][j];if(j - coins[i-1] >= 0)dp[i][j] = min(dp[i-1][j],dp[i][j - coins[i-1]] + 1 );}}return dp[n][amount] >= INF ? -1 : dp[n][amount];}
};

518. 零钱兑换 II

在这里插入图片描述

  1. 状态表示:经验+题目要求
    dp[i][j] 表示 从前i个硬币中挑选,总体积正好等于j,所有选法中,一共有多少种方法。

  2. 状态转移方程
    根据最后一步的状态:选还是不选。

在这里插入图片描述

  1. 初始化

在这里插入图片描述

class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<vector<int>> dp(n+1, vector<int>(amount+1));dp[0][0] = 1;for(int i = 1; i<=n; i++){for(int j = 0; j <= amount; j++){dp[i][j] += dp[i-1][j];if( j >= coins[i-1]){dp[i][j] += dp[i][j-coins[i-1]];}    }}return dp[n][amount];}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/431195.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

harmonyOS ArkTS最新跳转Navigation

文章目录 取消标题栏初始页面(load)设置为竖屏 自定义标题Tabs&TabContentTabs通过divider实现了分割线各种属性 图片下载 官方文档 Entry Component struct Index {State message: string Hello WorldState djs:number 5build() {Column(){Navigation(){}.title("g…

达梦-华为鲲鹏ARM架构下性能测试最佳实践

一、测试综述 1.1 测试目的 本次测试的目的是验证达梦数据库&#xff0c;在鲲鹏服务器下&#xff0c;不同服务器参数基于sysbench性能压力测试的表现。本次参数是根据为华为鲲鹏arm服务器调优十板斧内建议值调整 成长地图-鲲鹏开发套件开发文档-鲲鹏社区 1.2 通用指标 指标…

基于STM32的点滴输液报警器-设计说明书

设计摘要&#xff1a; 本文介绍了基于STM32微控制器的点滴输液报警器的设计与实现。点滴输液是医疗领域中常见的治疗方式&#xff0c;但输液速度的控制对患者的安全和治疗效果至关重要。因此&#xff0c;设计一种能够监测输液速度并在异常情况下发出警报的系统显得十分必要。基…

吴恩达深度学习笔记:卷积神经网络(Foundations of Convolutional Neural Networks)2.3-2.4

目录 第四门课 卷积神经网络&#xff08;Convolutional Neural Networks&#xff09;第二周 深度卷积网络&#xff1a;实例探究&#xff08;Deep convolutional models: case studies&#xff09;2.3 残差网络(ResNets)(Residual Networks (ResNets))2.4 残差网络为什么有用&am…

JavaEE: 深入探索TCP网络编程的奇妙世界(一)

文章目录 TCPTCP协议段落格式TCP相关机制TCP核心机制一: 确认应答32位序号32位确认序号后发先至问题 TCP TCP要比UDP更复杂一些~ TCP的全称为"传输控制协议".他负责对数据的传输进行一个详细的控制. TCP协议段落格式 源/目的端口号: 表示数据是从哪个进程来.到哪个…

Python 如何处理大文件的读取

Python 如何处理大文件的读取 在日常的开发工作中&#xff0c;我们经常会遇到处理大文件的需求。无论是读取日志文件、处理数据集&#xff0c;还是分析超大文本文件&#xff0c;大文件操作都是一个非常常见的挑战。尤其是在内存有限的环境中&#xff0c;直接将整个文件加载到内…

Docker配置代理解决pull超时问题

操作系统: CentOS Linux 8 Docker版本: 26.1.3 前置&#xff1a;你需拥有&#x1f431; 1. 配置 proxy.conf 1.1 创建配置文件目录 创建 docker.service.d&#xff0c;进入到 docker.service.d 中打开 proxy.conf (没有文件打开会自动创建)。 注意&#xff1a;每个人的路径可…

深度学习|误差逆传播:梯度速解

文章目录 引言链式法则误差逆传播加法的逆传播乘法的逆传播逆传播求梯度 SoftmaxWithLoss 层正向传播逆传播代码实现参考 结语 引言 我们知道训练神经网络模型的核心是以损失函数为基准来调整优化网络参数&#xff0c;使得网络的输出尽可能接近真实标签。在神经网络中&#xf…

Vue使用qrcodejs2-fix生成网页二维码

安装qrcodejs2-fix npm install qrcodejs2-fix核心代码 在指定父view中生成一个二维码通过id找到父布局 //通过id找到父布局let codeView document.getElementById("qrcode")new QRCode(codeView, {text: "测试",width: 128,height: 128,colorDark: #00…

Fyne ( go跨平台GUI )中文文档-小部件 (五)

本文档注意参考官网(developer.fyne.io/) 编写, 只保留基本用法 go代码展示为Go 1.16 及更高版本, ide为goland2021.2 这是一个系列文章&#xff1a; Fyne ( go跨平台GUI )中文文档-入门(一)-CSDN博客 Fyne ( go跨平台GUI )中文文档-Fyne总览(二)-CSDN博客 Fyne ( go跨平台GUI…

LeetcodeTop100 刷题总结(二)

LeetCode 热题 100&#xff1a;https://leetcode.cn/studyplan/top-100-liked/ 文章目录 八、二叉树94. 二叉树的中序遍历&#xff08;递归与非递归&#xff09;补充&#xff1a;144. 二叉树的前序遍历&#xff08;递归与非递归&#xff09;补充&#xff1a;145. 二叉树的后序遍…

移动数组中数字的方法(c语言)

1.移动一维数组中的内容;若数组中有n个整数&#xff0c;要求把下标从0到p(含p&#xff0c;p小于等于n-1&#xff09;的数组元素平移到数组的最后。 例如&#xff0c;一维数组中的原始内容为:1,2,3,4,5,6,7,8,9,10;p的值为3。 移动后&#xff0c;一维数组中的内容应为:5,6,7,8…

qm 命令:管理PVE虚拟机

一、命令简介 ​qm​ 是 Proxmox Virtual Environment (PVE) 中用于管理虚拟机的命令行工具。它允许用户创建、启动、停止、删除虚拟机&#xff0c;以及管理虚拟机的配置和状态。 ‍ 介绍 PVE Proxmox Virtual Environment (PVE) 是一个开源的虚拟化管理平台&#xff0c;专…

设计模式 享元模式(Flyweight Pattern)

享元模式 简绍 享元模式&#xff08;Flyweight Pattern&#xff09;是一种结构型设计模式&#xff0c;它的目的是通过共享技术来有效地支持大量细粒度的对象。享元模式可以极大地减少内存的使用&#xff0c;从而提高程序的性能。它特别适用于需要创建大量相似对象的场景&#…

QT 数据加密

一.使用环境 应该是通用的,此测试版本为如图 二.使用代码 1. 运行代码 QString data = "123abcAbc.-+";qDebug() << "加密:" << QAESEncryption::encodedText(data, "填入自己秘钥");qDebug() << "解密:" <…

C++STL的Stack的使用:STL栈和队列的使用介绍、leecode---最小栈、nowcoder---栈的压入、弹出序列等的介绍

文章目录 前言一、STL栈和队列的使用二、leetcode---最小栈三、nowcoder---栈的压入、弹出序列四、逆波兰表达式求值总结 前言 CSTL的Stack的使用&#xff1a;STL栈和队列的使用介绍、leecode—最小栈、nowcoder—栈的压入、弹出序列等的介绍 一、STL栈和队列的使用 #include …

服务器安装pytorch_geometric torch_scatter踩坑记录

conda create -n pyg python3.8.12 pip install torch1.13.0安装的版本如下 pip install torch-scatter pip install torch-sparse pip install torch-cluster pip install torch-spline-conv pip install torch-geometric2.2.0 pip install ipykernel python -m ipykernel i…

Adobe Illustrator吸管工具提取的颜色与原色之间存在色差

问题原因&#xff1a; 被提取颜色的对象是外部链接图片&#xff0c;对其提取的颜色会与AI中看到的颜色不同 如下图所示&#xff0c;中间的矩形与外部矩形的内部颜色存在色差 解决办法&#xff1a; 方法一&#xff1a;将该外部图片利用屏幕截图的形式&#xff0c;粘贴到AI中。…

2.以太网

局域网 局域网: Local Area Networks (LAN) 网络大小分类 局域网园区网(可以理解为企业网)城域网 广域网是一个网络连接的技术&#xff0c;并非多大范围的网络 网关 为局域网内的用户提供了一扇门&#xff0c;通过网关可以访问到别的网络。这个门&#xff0c;就叫网关 以…

部标(JT/T1078)流媒体对接说明

1.前言 最近在配合客户开发流媒体相关的服务的时候&#xff0c;整理了一些对接过程资料&#xff0c;这里做个分享与记录。流媒体的对接主要牵扯到4个方面&#xff1a; &#xff08;1&#xff09;平台端&#xff1a;业务端系统&#xff0c;包含前端呈现界面。 &#xff08;2&a…