多重背包问题与优化(裸题)(二)

简介: 多重背包问题与优化(裸题)

多重背包问题 II

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出一个整数,表示最大价值。

数据范围:

image.png

输入样例:

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例:

10

思路分析

image.png

#include <iostream>
using namespace std;
int main()
{
    int i, cnt = 1, temp = 0;
    for (i = 1; temp <= 2000; i ++ )
    {
        temp += cnt;
        cnt *= 2;
    }
    cout << i << endl;
    return 0;
}

运行结果为:12 ,即我们需要开的数组大小就为:12 × 1000 + 10 = 12010

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010, M = 12010, K = 1010;
int v[M], w[M];
int f[K][N];
int main()
{
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int v1, w1, s;
        cin >> v1 >> w1 >> s;
        int t = 1;
        while (t <= s)
        {
            cnt ++;
            v[cnt] = t * v1;
            w[cnt] = t * w1;
            s -= t;
            t *= 2;
        }
        if (s)
        {
            cnt ++;
            v[cnt] = s * v1;
            w[cnt] = s * w1;
        }
    }
    n = cnt;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max (f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

代码优化

既然是转换为了 01背包问题,故我们可以使用 01背包问题优化的思维去优化我们的空间(倒着for循环体积)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010, M = 12010;
int v[M], w[M];
int f[N];
int main()
{
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int v1, w1, s;
        cin >> v1 >> w1 >> s;
        int t = 1;
        while (t <= s)
        {
            cnt ++;
            v[cnt] = t * v1;
            w[cnt] = t * w1;
            s -= t;
            t *= 2;
        }
        if (s)
        {
            cnt ++;
            v[cnt] = s * v1;
            w[cnt] = s * w1;
        }
    }
    n = cnt;
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

多重背包问题 III

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

输出一个整数,表示最大价值。

数据范围:

image.png

输入样例:

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例:

10

思路分析

本题用到了单调队列(滑动窗口进行优化),对该知识点不了解或不熟悉的同学请先读博客:单调队列,附上一张y总讲课截图辅助理解:

3.png

image.png

代码

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010, M = 20010;
int v[N], w[N], s[N];
int f[N][M];
int q[M];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; i ++ ) 
    {
        for (int r = 0; r < v[i]; r ++ )
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i] )
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++;
                while (hh <= tt && f[i - 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[i - 1][j]) tt --;
                q[ ++ tt] = j;
                f[i][j] = f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

代码优化

和 多重背包问题 I 一样的优化方式,我们发现在计算f[i][j]的时候只使用了f[i−1][j],但是不可以使用 01背包的优化方法,因为我们使用的是 滑动窗口,这致使我们只能正向枚举体积。

滚动数组

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20010;
int f[2][N];
int q[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        int v, w, s;
        cin >> v >> w >> s;
        for (int r = 0; r < v; r ++ )
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v)
            {
                while (hh <= tt && j - q[hh] > s * v) hh ++;
                while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v * w <= f[(i - 1) & 1][j]) tt --;
                q[ ++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v * w;
            }
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

拷贝数组

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
int f[N], g[N];
int q[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        memcpy(g, f, sizeof f);
        int v, w, s;
        cin >> v >> w >> s;
        for (int r = 0; r < v; r ++ )
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v)
            {
                while (hh <= tt && j - q[hh] > v * s) hh ++;
                while (hh <= tt && g[q[tt]] + (j - q[tt]) / v * w <= g[j]) tt --;
                q[ ++ tt] = j;
                f[j] = g[q[hh]] + (j - q[hh]) / v * w;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}


目录
相关文章
|
存储 网络协议 文件存储
存储技术之FC 与 iSCSI 尖峰对决
  综述:   2003 年,互联网工程任务组(IETF)批准iSCSI(互联网SCSI)协议后,很多人开始将以太网作为分块存储网络使用(成为“基于IP 的存储”)。一直以来,人们采用iFCP和FCIP 等现有协议发送基于IP 的SCSI 命令行,主要允许FC 存储区域网络(SAN)通过IP 交换数据。凭借iSCSI,SCSI 命令行可以“端对端”地传送到世界各地的以太网中。
3481 0
pr2023安装包免费下载Premiere2023永久版安装包
包括Premiere Pro 2019、2020、2021、2022、2023等版本及其所有历史版本。目前功能最强大的视频编辑软件,是Adobe Premiere Pro,简称Pr。该软件不仅广泛应用于电影、电视节目的视频编辑制作,也是小视频等自媒体创作者剪辑制作视频、音频必不可少的工具。
5275 0
|
存储 Java 关系型数据库
java调用mysql存储过程
在 Java 中调用 MySQL 存储过程主要借助 JDBC(Java Database Connectivity)。其核心原理是通过 JDBC 与 MySQL 建立连接,调用存储过程并处理结果。具体步骤包括:加载 JDBC 驱动、建立数据库连接、创建 CallableStatement 对象、设置存储过程参数并执行调用。此过程实现了 Java 程序与 MySQL 数据库的高效交互。
|
存储 弹性计算 Cloud Native
云原生数据库的演进与应用实践
随着企业业务扩展,传统数据库难以应对高并发与弹性需求。云原生数据库应运而生,具备计算存储分离、弹性伸缩、高可用等核心特性,广泛应用于电商、金融、物联网等场景。阿里云PolarDB、Lindorm等产品已形成完善生态,助力企业高效处理数据。未来,AI驱动、Serverless与多云兼容将推动其进一步发展。
700 8
|
自然语言处理 IDE 开发工具
Xcode 26 (17A324) 正式版发布 - Apple 平台 IDE
Xcode 26 (17A324) 正式版发布 - Apple 平台 IDE
1853 0
|
编解码 人工智能 文字识别
5款知名度不高,但很好用的软件
本文推荐了5款小众但实用的软件工具:MouseInc可通过手势操作提升效率;TagSpaces以标签化管理文件,打破传统目录结构;燃精灵可检测微信空号,助力精准营销;GIMP作为开源图像编辑器,功能媲美Photoshop;File Converter支持200+格式互转,满足多种文件处理需求。这些工具虽知名度不高,却各具特色,值得尝试。
556 10
|
存储 Oracle 关系型数据库
Oracle存储过程插入临时表优化与慢查询解决方法
优化是一个循序渐进的过程,就像雕刻一座雕像,需要不断地打磨和细化。所以,耐心一点,一步步试验这些方法,最终你将看到那个让你的临时表插入操作如同行云流水、快如闪电的美丽时刻。
746 14
|
人工智能 数据可视化 vr&ar
操作系统的哲学:从命令行到图形界面的演变
【10月更文挑战第22天】 本文探讨了操作系统用户界面(UI)的发展,特别是从早期的命令行界面(CLI)到现代图形用户界面(GUI)的转变。通过分析这一转变背后的技术、社会和心理因素,我们不仅能够理解操作系统设计的演变,还能够洞察人类与技术互动方式的根本变化。文章采用总分总结构,先概述操作系统UI的历史发展,然后详细分析CLI和GUI的特点及其对用户的影响,最后总结这一转变对人类生活和技术发展的深远意义。
769 3
|
安全 Unix Linux
Centos虚拟机安装配置与MobaXterm工具及Linux常用命令(下)
Centos虚拟机安装配置与MobaXterm工具及Linux常用命令(下)
1434 0
|
数据采集 存储 监控
99%成功率背后:阿里云短信服务有何优势?
为什么短信会发送失败,如何提高短信发送成功率,本文将为您介绍短信发送成功率和阿里云短信服务如何保障企业短信稳定送达等相关知识。
1164 1
99%成功率背后:阿里云短信服务有何优势?