多重背包问题(一)

简介: AcWing算法提高课内容,本文讲解 动态规划

前言

AcWing算法提高课内容,本文讲解 动态规划

本篇包括以下题目:

⭐️ 多重背包问题 I

⭐️ 多重背包问题 II

⭐️ 多重背包问题 III

⭐️ AcWing 1019. 庆功会

写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来,博主会立即改正!望大家海涵



多重背包问题 I

题目要求

题目描述:

image.png

输入格式:

image.png

输出格式:

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

数据范围:

image.png

输入样例:

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

输出样例:

10

思路分析

数据范围很小,暴力枚举即可,不需要过多操作,f[i][j]代表的是只从前 i 件物品中选,且总体积不超过 j的价值最大值。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][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 j = 0; j <= m; j ++ )
            for (int k = 0; k <= s && k * v <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v] + k * w);
    }
    cout << f[n][m] << endl;
    return 0;
}

代码优化

image.png

滚动数组


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[2][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 j = 0; j <= m; j ++ )
            for (int k = 0; k <= s && k * v <= j; k ++ )
                f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - k * v] + k * w);
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

拷贝数组

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

逆循环优化

逆循环的优化方式和 01 背包的优化是相同的,原理也是一致的,对于体积逆序枚举即可实现,这样的优化方法可真正实现仅用一维数组表示二维变量:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[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 j = m; ~j; j -- )
            for (int k = 0; k <= s && k * v <= j; k ++ )
                f[j] = max(f[j], f[j - k * v] + k * w);
    }
    cout << f[m] << endl;
    return 0;
}

多重背包问题 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;
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;
}


#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循环体积)




目录
相关文章
|
机器学习/深度学习 数据挖掘 数据处理
从mice到missForest:常用数据插值方法优缺点
从mice到missForest:常用数据插值方法优缺点
1649 1
|
Ubuntu Unix Linux
Linux Ubuntu man文档的图文安装教程
Linux Ubuntu man文档的图文安装教程
741 0
|
8月前
|
人工智能 缓存 安全
OpenClaw“龙虾”深度解析:AI智能体能力边界、成本真相与阿里云|本地部署实战指南
2026年,AI智能体(Agent)已从概念走向落地,OpenClaw(昵称“龙虾”)凭借自主任务闭环、跨软件执行与插件扩展能力,成为新一代自主智能体的标杆产品。它不再局限于文本交互,而是能理解目标、拆解步骤、调用工具、校验结果,实现从聊天助手到自动化执行系统的跨越。但高能力背后,是高昂的Token消耗、权限安全与企业落地难题。本文将系统解析OpenClaw的技术架构、代价真相与安全方向,并提供2026年阿里云部署、本地MacOS/Linux/Windows11部署、阿里云千问API与免费Coding Plan API配置全流程,附代码命令与常见问题解答,覆盖个人与企业级完整落地方案。
2923 5
|
人工智能 小程序 安全
小程序跨平台框架未来的发展趋势是什么?
小程序跨平台框架未来的发展趋势是什么?
553 128
|
7月前
|
存储 人工智能 自然语言处理
AI 应用软件的开发
AI应用已从“聊天框”升级为具备感知、决策与执行能力的智能体(Agent)。本文系统梳理四大类型(AIGC、RAG、AI Agents、嵌入式AI)、核心架构及国内五阶段开发流程,强调模型、业务与合规的深度集成。(239字)
|
9月前
|
人工智能 自然语言处理 前端开发
写了10万行代码,却毁在配色上?这套指令让后端直男秒变设计总监
这是一篇专为后端及全栈开发者定制的实用指南,旨在解决开发者“代码强但审美弱”的痛点。文章提供了一套核心AI指令,能将DeepSeek等AI变成专业UI设计顾问,快速生成符合大厂规范(Design Token)的配色体系。通过一个后台管理系统的实战案例,演示了如何用AI将“土味”界面瞬间升级为专业级UI,让开发者无需学习设计理论也能搞定高颜值配色。
1004 4
|
存储 缓存 编解码
阿里云服务器实例规格怎么选?经济型、通用算力型、计算型、通用型、内存型场景化选购指南
阿里云服务器的实例规格有经济型、通用型、计算型、内存型、通用算力型、大数据型、本地SSD型、高主频型、突发型、共享型等不同种类的实例规格,以满足不同用户和业务场景的需求。对于初次接触阿里云服务器的用户来说,如何选择合适的实例规格成为了一个重要的问题。本文将为大家解析阿里云的经济型、通用算力型、计算型、通用型和内存型实例规格的主要性能和适用场景情况,帮助用户根据实际需求选择合适的云服务器实例。
1256 10
|
11月前
|
运维 监控 安全
容器跑起来才是危险的开始:聊聊 Falco + eBPF + 行为检测这套“运行时安全真功夫”
容器跑起来才是危险的开始:聊聊 Falco + eBPF + 行为检测这套“运行时安全真功夫”
335 9
|
JavaScript 前端开发 搜索推荐
Nuxt4.0初体验:一个简约、精美、现代化的个人站点导航!
这篇文章介绍了作者使用Nuxt 4.0重构个性化站点导航网站的经历,阐述了Nuxt 4.0的新特性和优势,如更清晰的项目结构、更好的TypeScript体验、更快的CLI和开发速度等,并且分享了重构过程中的体验和项目完成效果。同时,作者还对比了Nuxt.js与Next.js两个框架的优劣,表达了自己对Nuxt.js的偏好。
927 0
Nuxt4.0初体验:一个简约、精美、现代化的个人站点导航!