算法:完全背包问题dp

文章目录

      • 一、完全背包问题的特征
      • 二、定义状态
      • 三、状态转移
      • 四、降维优化
      • 五、参考例题
        • 5.1、Acwing:3.完全背包问题
        • 5.2、Acwing:900. 整数划分

在这里插入图片描述

一、完全背包问题的特征

完全背包问题是动态规划中的一种经典问题,它的主要特征可以总结如下:

  1. 无限使用物品:与0-1背包问题不同,其每种物品只能使用一次,而完全背包问题允许每种物品被无限次选取。

  2. 背包容量限制:存在一个容量限制W,所有选取的物品总重量不能超过这个限制。

  3. 目标函数目标是在不超过背包容量的前提下,最大化背包内物品的总价值。

  4. 复杂度:完全背包问题的时间复杂度和空间复杂度取决于具体的实现方法,通常时间复杂度为O(NW),其中N是物品数量,W是背包容量。通过优化,空间复杂度可以降低到O(W)

二、定义状态

  • 定义dp[i][j]表示,考虑前i个物品且背包容量为j时的最大价值。

三、状态转移

  • dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+price[i])
  • 即背包容量为j时,考虑前i个物品的最大价值从两个方面转移而来:
    • dp[i-1][j]:不加入物品i时,容量为j的背包利益最大值。
    • dp[i][j-weight[i]]+price[i]:加入物品i时,容量为j的背包利益最大值。

我们需要特别注意这里和0-1背包的区别,
0-1背包:dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+price[i]),因为0-1背包每个物品要么放要么不放,而完全背包问题每个物品可以放置多次,因此转移时是从考虑物品i的情况下转移的。

for(int j=weight[0];j<=V;++j)
	dp[0][j]=dp[0][j-weight[0]]+price[0];
for(int i=1;i<N;++i)
for(int j=weight[i];j<=V;++j)
	dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+price[i]);

四、降维优化

考虑到状态转移的时候,我们是一个物品一个物品考虑的,相当于二维数组中一行一行考虑的,当前状态只需要用到之前的状态,因此我们可以进行降维优化。将空间降低到一维:

    dp[0]=0;
    for(int i=0;i<N;++i){//考虑第i个物品
        for(int j=weight[i];j<=V;++j){
            dp[j]=max(dp[j],dp[j-weight[i]]+price[i]);
        }
    }

五、参考例题

5.1、Acwing:3.完全背包问题

模板题
3.完全背包问题

#include<bits/stdc++.h>
using namespace  std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N,V;
    cin>>N>>V;
    
    vector<int> volume(N);
    vector<int> price(N);
    for(int i=0;i<N;++i){
        cin>>volume[i]>>price[i];
    }
    
    vector<int> dp(V+1);
    dp[0]=0;
    
    for(int i=0;i<N;++i){//考虑第i个物品
        for(int j=volume[i];j<=V;++j){
            dp[j]=max(dp[j],dp[j-volume[i]]+price[i]);
        }
    }
    
    cout<<dp[V];
    return 0;
}
5.2、Acwing:900. 整数划分

900.整数划分
整数划分问题可以转换成,完全背包问题。即:
对于体积为n的背包,有1~n ,n个物品,每个物品的体积为其编号大小,求体积为n的背包能被装满的不同物品放置种类数。
整数划分问题解析

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

政安晨:【深度学习神经网络基础】(四)—— 自组织映射

目录 自组织映射和邻域函数 理解邻域函数 墨西哥帽邻域函数 计算SOM误差 政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 收录专栏: 政安晨的机器学习笔记 希望政安晨的博客能够对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

APx500音频分析仪硬件简介

两通道模拟输出&#xff0c;两通道或以上的模拟输入接口 线性编码数字音频接口&#xff08;AES/EBU,TOSLINK,SPDIF&#xff09;Linear PCM 脉冲密度调制码流&#xff08;需要APx-PDM选件支持&#xff09; Bluetooth蓝牙音频码流&#xff08;需APx-BT选件支持&#xff09; 最…

打印月历 Open Judge

题面链接: http://noi.openjudge.cn/ch0113/24/ 题目描述: 评析: 大模拟题&#xff0c;考察的是你的耐心和毅力&#xff01;很不错的模拟题练习题&#xff0c;小白(like me)可以练一练 思路: 先一个月一个月的模拟&#xff0c;求出来题目问的这个一年的这一个月的第一天是星期…

C#互联网区域医学检验中心云LIS系统源码

云LIS联通四级&#xff08;市、县、乡、村&#xff09;检验服务网构建互联网检验服务新体系落地检验资源区域共享建设。云LIS系统是一种基于云计算技术的区域实验室信息管理系统&#xff0c;它的主要功能是管理实验室中的各种信息数据&#xff0c;包括样品数据、检测结果、仪器…

多视觉传感器协同弱小目标检测

源自&#xff1a;指挥与控制学院 作者&#xff1a;王田&#xff0c; 程嘉翔&#xff0c; 刘克新&#xff0c;王薇&#xff0c; 吕金虎 “人工智能技术与咨询” 发布 摘 要 多视觉传感器协同对空实现全区域覆盖的弱小目标检测&#xff0c;在近距离防空领域中具有重要意义。…

酷开科技不断深耕智能电视领域,用酷开系统带给消费者更多可能性

在这个网络快速发展的时代&#xff0c;电视行业也发生了巨大变革。与以往单纯的“看”电视不同&#xff0c;人们不再满足于现有的状态&#xff0c;消费者对电视娱乐的追求更加丰富&#xff0c;这也就带给智能电视产业无限的发展可能。酷开科技瞄准这一产业趋势&#xff0c;不断…

Golang | Leetcode Golang题解之第18题四数之和

题目&#xff1a; 题解&#xff1a; func fourSum(nums []int, target int) (quadruplets [][]int) {sort.Ints(nums)n : len(nums)for i : 0; i < n-3 && nums[i]nums[i1]nums[i2]nums[i3] < target; i {if i > 0 && nums[i] nums[i-1] || nums[i]…

VLAN间的通信

目录 原理概述 实验目的 实验内容 实验拓扑 1.基本配置 2.使用VLANIF接口实现VLAN间的通信 3.使用VLAN聚合实现VLAN间的通信。 原理概述 通常情况下&#xff0c;如果不采用一些特殊的方法&#xff08;如采用Hybrid端口的方法&#xff09;&#xff0c;不同的VLAN之间是不…

力扣--动态规划完全背包/深度优先08.11.零币

如果暴力的深度优先&#xff1a; class Solution {// 定义硬币的面值数组int fangx[4] {25, 10, 5, 1};// 计数变量&#xff0c;用于记录配合得到 n 的方法数long long count 0;// 定义深度优先搜索函数// now: 当前总值// n: 目标总值// notbig: 上一次选择的硬币面值索引…

PCB学习记录-----入门基础知识

一、搭建环境 1.下载嘉立创EDA 软件下载 - 嘉立创EDA (lceda.cn) 选专业版 在线编辑&#xff1a;嘉立创EDA(专业版) - V2.1.45 (lceda.cn) 官方教程&#xff1a;立创EDA专业版-使用教程 (lceda.cn) 2.新建工程 文件-新建-项目&#xff0c;右键Board1可以重命名&#xff…

Debian 12.0安装NVM管理器

cd到一个自己创建的目录 要在Debian 12.0上安装 Node Version Manager&#xff08;NVM&#xff09;来管理 Node.js 版本&#xff0c;您可以按照以下步骤进行操作&#xff1a; 首先&#xff0c;您需要使用 cURL 下载 NVM 安装脚本。在终端中运行以下命令&#xff1a; curl -o…

读博做FPGA上的AI加速能不能搞啊?

从企业的角度来看&#xff0c;选择在FPGA上进行AI加速仍然有其一定的优势和适用场景&#xff0c;但也有一些挑战需要考虑。我这里有一套嵌入式入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习嵌入式&#xff0c;不妨点个关注&#xff0c;给…

使用Datax自定义采集组件Reader/Writer实现国产数据库支持以及_Datax数据清洗/过滤规则功能自定义---大数据之DataX工作笔记007

我们基于datax来做的自己的数据采集系统,现在基本的数据采集已经实现了,也就是调用datax的数据采集能力,实现在已支持的数据库之间同步数据.我们是基于datax-web实现的,里面都有开源的代码了,可以分析以后拿过来用,这个过程并不复杂,而且,结合xxljob的web那个开源项目,也可以让…

S19文件解析

目录 一、概述 二、S19文件解析 三、举例 一、概述&#xff1a; Motorola S-record是一种文件格式&#xff0c;由摩托罗拉在20世纪70年代中期为Motorola 6800处理器创建&#xff0c;以ASCII文本形式传达二进制信息的十六进制值&#xff0c;其文件格式也可能为SRECORD&#xf…

如何使用宝塔面板搭建MySQL数据库并实现无公网IP远程访问

文章目录 前言1.Mysql服务安装2.创建数据库3.安装cpolar3.2 创建HTTP隧道 4.远程连接5.固定TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 宝塔面板的简易操作性,使得运维难度降低,简化了Linux命令行进行繁琐的配置,下面简单几步,通过宝塔面板cp…

Macos 部署自己的privateGpt(2024-0404)

Private Chatgpt 安装指引 https://docs.privategpt.dev/installation/getting-started/installation#base-requirements-to-run-privategpt 下载源码 git clone https://github.com/imartinez/privateGPT cd privateGPT安装软件 安装&#xff1a; Homebrew /bin/bash -c…

《C语言深度解剖》(3):探索函数递归、传值、传址调用的奥秘

&#x1f921;博客主页&#xff1a;醉竺 &#x1f970;本文专栏&#xff1a;《C语言深度解剖》 &#x1f63b;欢迎关注&#xff1a;感谢大家的点赞评论关注&#xff0c;祝您学有所成&#xff01; ✨✨&#x1f49c;&#x1f49b;想要学习更多数据结构与算法点击专栏链接查看&am…

Linux锁的使用

一、临界资源与临界区 多线程会共享例如全局变量等资源&#xff0c;我们把会被多个执行流访问的资源称为临界资源&#xff0c;我们是通过代码访问临界资源的&#xff0c;而我们访问临界资源的那部分代码称为临界区。 实现一个抢票系统 只有一个线程抢票时 #include <ios…

【二分查找】Leetcode 寻找峰值

题目解析 162. 寻找峰值 题目中有一个很重要的提示&#xff1a;对所有有效的i都存在nums[i] ! nums[i1],因此这道题不需要考虑nums[mid] 和 nums[mid1]之间的相等与否的关系 算法讲解 1. 暴力枚举 我们按照顺序判断每个数字是否是当前的峰值&#xff0c;如果是直接返回&#…

【WEEK7】 【DAY1】索引【中文版】

2024.4.8 Monday 目录 7.索引7.1.内涵7.2.索引的作用7.3.索引的分类7.3.1.主键索引&#xff08;PRIMARY KEY&#xff09;7.3.1.1.主键 : 某一个属性组能唯一标识一条记录7.3.1.2.特点 : 7.3.2.唯一索引&#xff08;UNIQUE KEY&#xff09;7.3.2.1.作用 : 避免同一个表中某数据…