算法学习笔记(8.8)-多重背包

目录

Question:

 思路解析:

代码示例

 多重背包的优化问题:

 1.二进制优化

代码示例:

 2.单调队列优化(滑动窗口)

代码示例 

Question:

4. 多重背包问题 I - AcWing题库icon-default.png?t=N7T8https://www.acwing.com/problem/content/description/4/

多重背包简单来说其实就是一个背包问题的变式,到底可以怎么去理解多重背包呢,说白了其实就是01背包和完全背包的结合,主要的优化方法就是二进制分组优化,单调队列优化方法

 思路解析:

我们到底该怎么去理解转化呢,我们可以这样去思考问题,同一件物品可以重复去拿,10个相同的苹果体积为2价值为3,我们可以看成一个大苹果,体积为10*2,价值为10*3,此时就转化成了完全问题,选还是不选的问题,此时的选与不选是要在同一种物品的不同个体间做选择,直至我们的背包无法装下我们的这种物品。(此时的对于转化成完全的限制条件又是什么呢,我们只需要考虑我们的物品的 数量 * 体积 >= 背包的总体积,就可以转化成完全背包问题,我们可以在同种物品的不同个体间进行选择);对于 数量 * 体积 < 背包的体积,我们又该如何去考虑呢,我们可以这样子去思考,如果我们可以将相同的很多件物品看作一件,这不就转化成了0-1背包问题嘛,此时我们需要取枚举,我们实际需要拿多少个K,也就是所谓的当前背包的体积J > K * V[I],我们就可以全部的K装进背包。

(针对于代码间的问题说明,我们均采用了空间优化的方法,对于0-1背包而言我们需要考虑覆盖问题,但是完全背包不需要考虑)

代码示例

// c++ 代码示例

#include <iostream>
#include <algorithm>

using namespace std ;

const int MAXN = 101 ;
int n, V ;
int v[MAXN], w[MAXN], s[MAXN] ;
int f[MAXN] ;

int main()
{
    // 获取基本的输入
    cin >> n >> V ;
    for (int i = 1 i <= n ; i++)
    {
        cin >> v[i] >> w[i] >> s[i] ;
    }
    // 以下代码均是空间优化后的
    // 0-1背包和完全背包的转化过程思想,遍历每一种物品    
    for (int i = 1 ; i <= n ; i++)
    {     
        if (s[i] * v[i] >= V)
        {
            for (int j = v[i] ; j <= V ; j++)
            {
                f[j] = max(f[j], f[j - v[i]] + w[i]) ;
            }
        }
        // 0-1背包
        else
        {
            for (int j = V ; j >= v[i] ; j--)    
            {
                for (int k = s[i] ; k >= 0 ; k--)
                {
                    if (j >= k * v[i])
                    {
                        f[j] = max(f[j], f[j - k * v[i]] + k * w[i]) ;
                    }
                }
            }
        }
    }
    cout << f[V] ;
    return 0 ;
}
# python 代码示例

n,V = map(int,input().split())

v = [0] * (101 + 1)
w = [0] * (101 + 1)
s = [0] * (101 + 1)
f = [0] * (101 + 1)

for i in range(1, n + 1) :
    v[i], w[i], s[i] = map(int, input().split())

for i in range(1, n + 1) :
    if (s[i] * v[i] >= V) :
        for j in range(v[i], V + 1) :
            f[j] = max(f[j], f[j - v[i]] + w[i])
    else :
        for j in range(V, v[i] - 1, -1) :
            for k in range(s[i], -1, -1) :
                if (j >= k * v[i]) :
                    f[j] = max(f[j], f[j - k * v[i]] + k * w[i])

print(f[V])

 基本思想:比如第i件物品有s个,我可以把相同种类的物品的进行合并,比如我拿出两件合并出一个新的物品,我拿出三件合并出一个新的物品,以此类推,我拿出s个合并出一个新的物品。基于这种思想,我们把第i件的s个物品转换为s种体积各不相同的物品,然后在用01背包的思想,求出最优解!

#include <iostream>
#include <algorithm>
using namespace std ;

int N, V ;
int dp[1010] ;

int main()
{
    cin >> N >> V ;
    int v, w, s ;
    for (int i = 1 ; i <= N ; i++)
    {
        cin >> v >> w >> s ;
        for (int j = V ; j > 0 ; j--)
        {
            for (int k = 1 ; k <= s && k * v <= j ; k++)
            {
                dp[j] = max(dp[j], dp[j - k * v] + k * w) ;
            }
        }
    }
    cout << dp[V] ;
    return 0 ;
}

 多重背包的优化问题:

 1.二进制优化

5. 多重背包问题 II - AcWing题库icon-default.png?t=N7T8https://www.acwing.com/problem/content/5/

原理:
一个数字,我们可以按照二进制来分解为1 + 2 + 4 + 8 …… +2^n + 余数

十进制数字7,可以从二进制100,010,001做加和得到即111,001为1,010为2,100为4,也就是1、2、4,用1、2、4可以表示1~7中任意一个数。
再比如,10,可以分为1,2,4,3这个三是怎么来的呢? 3就是余数!

通过上述原理,我们可以把第i件物品的s件,按二进制思想分为1,2,4…到剩余。这样从复杂度为s,降到了(log2S)。时间复杂度为O(V*Σlog n[i])。

代码示例:
// c++代码示例
#include <iostream>
#include <algorithm>

using namespace std ;

const int MAXN = 1e5 + 10 ;

int n , V ;
int v[MAXN], w[MAXN] ;
int f[MAXN] ;

int main()
{
    cin >> n >> V ;
    int cnt = 0 ;
    for (int i = 1 , a, b, s ; i <= n; i++)    
    {
        cin >> a >> b >> s ;
        int k = 1 ;
        while (k <= s)
        {
            v[++cnt] = k * a ;
            w[cnt] = k * b ;
            s -= k ;
            k *= 2 ;
        }
        if (s)
        {
            v[++cnt] = s * a ;
            w[cnt] = s * b ;
        }
    }
    for (int i = 1 ; i <= cnt ; i++)
    {
        for (int j = V ; j >= v[i] ; j--)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]) ;
        }
    }
    cout << f[V] ;
    return 0 ;
}
#include <iostream>
#include <algorithm>

using namespace std ;
const int maxn = 6e3 + 10 ;

int n , m , ans ;

int f[maxn] ;

int main()
{
    cin >> n >> m ;
    
    for (int i = 1 ; i <= n ; i++)
    {
        int v, w, s ;
        cin >> v >> w >> s ;
        for (int k = 1 ; k <= s ; k *= 2)
        {
            for (int j = m ; j >= k * v ; j--)
            {
                f[j] = max(f[j], f[j - k * v] + k * w) ;
            }
            s -= k ;
        }
        if (s)
        {
            for (int j = m ; j >= s*v ; j--)
            {
                f[j] = max(f[j], f[j - s * v] + s * w) ;
            }
        }
    }
    cout << f[m] ;
    return 0 ; 
}

 2.单调队列优化(滑动窗口)

6. 多重背包问题 III - AcWing题库icon-default.png?t=N7T8https://www.acwing.com/problem/content/6/

 利用单调队列优化动态规划的状态转移过程。它通过维护一个单调递减的队列,确保在每次状态转移时可以高效地找到最优的前驱状态,从而减少时间复杂度。

我们可以这样理解这个问题,就是每一次拿到该种类的物品的时候,就把这种物品的思考为0-v-1的单调队列,然后利用双指针维护最优解,需要考虑窗口维护的时候,我们要知道单调队列里里面存储到底是什么其实是j , j + v , j + 2 * v……等,到最后进行维护的便是这个单调队列,最优解是{   f [j], f [j+v], f [j+2*v], f [j+3*v], ... , f [j+k*v]   } 中的最大值,稍微转化一下f [j+k*v] = max( f [j], f[j+v] - w,..., f [j+k*v] - k*w) + k*w,我们就可以通过一个中介数组进行动态更新了。q数组中保存了上述写的 当 f [j+k*v] - k*w 最大时的下标,入队前如果队首不在滑动窗口内,队首出队,每次入队元素如果比队列中元素大,就弹出队尾

代码示例 
// c++ 代码示例

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std ;

const int MAXN = 20010 ;
int n ,f[MAXN], q[MAXN], pre[MAXN];

int main()
{
    int n, V ;
    cin >> n >> V ;
    for (int i = 1, v ,w ,s ; i <= n ; i++)    
    {
        cin >> v >> w >> s ;
        memcpy(pre, f, sizeof(f)) ;
        for (int j = 0 ; j < v ; j++)
        {
            int hh = 0 , tt = -1 ;
            for (int t = j ; t <=V ; t += v)
            {
                if (hh <= tt && t - s * v > q[hh])
                {
                    hh++ ;
                }
                while (hh <= tt && pre[q[tt]] - (q[tt] - j) / v * w <= pre[t] - (t - j) / v * w)
                {
                    tt-- ;
                }
                if (hh <= tt)
                {
                    f[t] = max(f[t], pre[q[hh]] + (t - q[hh]) / v * w) ;
                }
                q[++tt] = t ;
            }
        }
    } 
    cout << f[V] ;
    return 0 ;
}

 

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

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

相关文章

嵌入式面试总结

直接I/O——绕过内核缓冲 Linux允许应用程序在执行文件I/O操作时绕过内核缓冲区&#xff0c;从用户空间直接传递数据到文件或磁盘设备。 在调用open()函数时&#xff0c;直接添加O_DIRECT标志。 某些应用程序的作用是测试磁盘设备的读写速率&#xff0c;那么就要保证read等操…

【计算机毕业设计】890社区宠物管理与服务系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

Android APP 音视频(02)MediaProjection录屏与MediaCodec编码

说明&#xff1a; 此MediaProjection 录屏和编码实操主要针对Android12.0系统。通过MediaProjection获取屏幕数据&#xff0c;将数据通过mediacodec编码输出H264码流&#xff08;使用ffmpeg播放&#xff09;&#xff0c;存储到sd卡上。 1 MediaProjection录屏与编码简介 这里…

Minos 多主机分布式 docker-compose 集群部署

参考 docker-compose搭建多主机分布式minio - 会bk的鱼 - 博客园 (cnblogs.com) 【运维】docker-compose安装minio集群-CSDN博客 Minio 是个基于 Golang 编写的开源对象存储套件&#xff0c;虽然轻量&#xff0c;却拥有着不错的性能 中文地址&#xff1a;MinIO | 用于AI的S3 …

【odoo17 | Owl】前端js钩子调用列表选择视图

概要 在我们选择多对一或者多对多字段的时候&#xff0c;经常看到可以弹出列表弹窗让人一目了然的效果&#xff0c;效果如下&#xff1a; 那么&#xff0c;这种效果是odoo本身封装好的组件&#xff0c;我们在平时的前端界面开发的时候&#xff0c;既不是后端视图的情况下&#…

Apache ShardingSphere Proxy5.5.0实现MySQL分库分表与读写分离

1. 前提准备 1.1 主机IP:192.168.186.77 version: 3.8services:mysql-master:image: mysql:latestcontainer_name: mysql-masterenvironment:MYSQL_ROOT_PASSWORD: 123456MYSQL_USER: masterMYSQL_PASSWORD: 123456MYSQL_DATABASE: db1 ports:- "3306:3306&quo…

SearchGPT 搜索引擎发布:让信息检索变得简单

如今的互联网时代&#xff0c;我们每天都在与海量数据搏斗。无论是学习、工作还是生活&#xff0c;我们都需要快速准确地获取所需信息。然而&#xff0c;传统搜索引擎往往让人感到力不从心&#xff1a;关键词需要精准&#xff0c;结果泛滥成灾&#xff0c;有用信息如大海捞针。…

内网对抗-隧道技术篇防火墙组策略HTTP反向SSH转发出网穿透CrossC2解决方案

知识点&#xff1a; 1、C2/C2上线-CrossC2插件-多系统平台支持 2、隧道技术篇-应用层-SSH协议-判断&封装&建立&穿透 3、隧道技术篇-应用层-HTTP协议-判断&封装&建立&穿透隧道技术主要解决网络通讯问题&#xff1a;遇到防火墙就用隧道技术&#xff0c;…

vue elementui 在table里使用el-switch

<el-table-columnprop"operationStatus"label"状态"header-align"center"align"center"><template slot-scope"scope"><el-switch active-value"ENABLE" inactive-value"DISABLE" v-mod…

麦歌恩MT6521-第三代汽车磁性角度传感器芯片

磁性编码芯片 -在线编程角度位置IC 描述&#xff1a; MT6521是麦歌恩微电子推出的新一代基于水平霍尔及聚磁片(IMC)技术原理的磁性角度和位置检测传感器芯片。该芯片内部包含了两对互成90放置的水平霍尔阵列及聚磁片&#xff0c;能够根据不同的型号配置来实现对XY&#xff0…

Idea2024 创建Meaven项目没有src文件夹

1、直接创建 新建maven项目&#xff0c;发现没有src/main/java 直接新建文件夹&#xff1a;右击项目名->new->Directory 可以看到idea给出了快捷创建文件夹的选项&#xff0c;可以根据需要创建&#xff0c;这里点击src/main/java 回车&#xff0c;可以看到文件夹已经创建…

OSPF概述

OSPF OSPF属于内部网关路由协议【IGP】 用于单一自治系统【Autonomous System-AS】内决策路由 自治系统【AS】 执行统一路由策略的一组网络设备的组合 OSPF概述 为了适应大型的网络&#xff0c;OSPF在AS内划分多个区域 每个OSPF路由器只维护所在区域的完整的链路状态信息 …

基于PaddleClas的人物年龄分类项目

目录 一、任务概述 二、算法研发 2.1 下载数据集 2.2 数据集预处理 2.3 安装PaddleClas套件 2.4 算法训练 2.5 静态图导出 2.6 静态图推理 三、小结 一、任务概述 最近遇到个需求&#xff0c;需要将图像中的人物区分为成人和小孩&#xff0c;这是一个典型的二分类问题…

【数据结构】手把手教你单链表(c语言)(附源码)

&#x1f31f;&#x1f31f;作者主页&#xff1a;ephemerals__ &#x1f31f;&#x1f31f;所属专栏&#xff1a;数据结构 目录 前言 1.单链表的概念与结构 2.单链表的结构定义 3.单链表的实现 3.1 单链表的方法声明 3.2 单链表方法实现 3.2.1 打印链表 3.2.2 创建新…

C++ | Leetcode C++题解之第275题H指数II

题目&#xff1a; 题解&#xff1a; class Solution { public:int hIndex(vector<int>& citations) {int n citations.size();int left 0, right n - 1;while (left < right) {int mid left (right - left) / 2;if (citations[mid] > n - mid) {right m…

使用Diffusion Models进行街景视频生成

Diffusion Models专栏文章汇总:入门与实战 前言:街景图生成相当有挑战性,目前的文本到视频的方法仅限于生成有限范围的场景的短视频,文本到3D的方法可以生成单独的对象但不是整个城市。除此之外街景图对一致性的要求相当高,这篇博客介绍如何用Diffusion Models执行街景图生…

JAW:一款针对客户端JavaScript的图形化安全分析框架

关于JAW JAW是一款针对客户端JavaScript的图形化安全分析框架&#xff0c;该工具基于esprima解析器和EsTree SpiderMonkey Spec实现其功能&#xff0c;广大研究人员可以使用该工具分析Web应用程序和基于JavaScript的客户端程序的安全性。 工具特性 1、动态可扩展的框架&#x…

Unity UGUI 之 图集

本文仅作学习笔记与交流&#xff0c;不作任何商业用途 本文包括但不限于unity官方手册&#xff0c;唐老狮&#xff0c;麦扣教程知识&#xff0c;引用会标记&#xff0c;如有不足还请斧正 本文在发布时间选用unity 2022.3.8稳定版本&#xff0c;请注意分别 1.什么是图集 精灵图…

C语言玩一下标准输出——颜色、闪烁、加粗、下划线属性

文章目录 C语言玩一下标准输出——颜色、闪烁、加粗、下划线属性转换Tip切换内容介绍显示方式字体色背景色 常用光标控制附示例和运行结果 C语言玩一下标准输出——颜色、闪烁、加粗、下划线属性 标准输出格式其属性可控制&#xff0c;控制由一系列的控制码指定。标准输出函数可…

一个C++模板工厂的编译问题的解决。针对第三方库的构造函数以及追加了的对象构造函数。牵扯到重载、特化等

一窥模板的替换和匹配方式&#xff1a;偏特化的参数比泛化版本的还要多&#xff1a;判断是不是std::pair&#xff1c;,&#xff1e;。_stdpair模板参数太多-CSDN博客 简介 在一个项目里&#xff0c;调用了第三封的库&#xff0c;这个库里面有个类用的很多&#xff0c;而且其构…