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

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

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



目录
相关文章
|
7月前
|
SQL 存储 关系型数据库
【第1天】每天一个MySQL知识点,百日打怪升级
本系列以“每天一个知识点”形式,系统讲解MySQL核心原理。首日聚焦Client/Server通信流程,详解三层架构(连接层→SQL层→存储引擎层)、连接管理、查询解析优化及执行计划,直击面试高频考点,助你从CRUD进阶到懂原理、能排障。(239字)
399 0
|
8月前
|
存储 监控 数据处理
浏览器自动化能干嘛?三个零门槛实操案例
本文介绍零代码浏览器自动化工具如何解放重复劳动:教培老师作业归档、个人账单统计、打印店接单等场景,仅需拖拽配置即可实现全自动操作。无需编程,识别按钮、提取数据、处理文件、自动回复一气呵成,每天轻松省下数小时。(239字)
|
25天前
|
运维 安全 Linux
告别云端账单!Ollama本地部署LLM完全指南:从环境变量到命令行,再到Python/curl实战代码一网打尽
当每一次Token消耗都在蚕食你的预算,当每一条数据上传云端都在挑战隐私红线——是时候把大模型"请回家"了。本文将带你从零构建完全离线的本地大模型运行环境,手把手敲定环境变量、核心命令与实战代码,让你彻底告别云端按量扣费的焦虑。而如果你同时需要云端弹性算力作补充,也可随时前往‌阿里云百炼大模型服务平台页面‌了解一站式MaaS方案。
263 1
|
30天前
|
存储 人工智能 调度
AI Infra全栈拆解:大模型应用背后的基础设施,算力集群、网络、存储与服务治理体系26.0
AI Infra(人工智能基础设施)是支撑大模型训练、微调、推理与运维的软硬件协同体系,涵盖GPU集群、高速网络、分布式存储、容器编排、模型管理及全链路可观测性。它超越传统云原生架构,专为显存密集、通信敏感的大模型场景优化,核心目标是提效、可靠、隔离与可观测。
412 1
|
2月前
|
人工智能 JavaScript API
Qwen3.8‑Omni‑Flash模型指南:输入输出价格、详细介绍、免费Token领取、模型能力及API接入说明
Qwen3.8‑Omni‑Flash是阿里云推出的原生全模态大模型,支持1M长序列及文本、图像、音视频多模态输入与理解,具备视频问答、剪辑、AI音乐生成等Agentic能力。百炼平台免费赠送100万Tokens,兼容OpenAI/DashScope协议,开箱即用。在阿里云百炼官网:https://t.aliyun.com/U/fPVHqY 免费领取千万Tokens
498 0
|
4月前
|
人工智能 自然语言处理 数据挖掘
从39元包月到企业级智能体:Qwen3.8-Max-Preview架构、计费、部署一站式教程
当下AI落地赛道中,开发者长期被两类问题桎梏开发进度。其一,轻量化开源基座模型推理上限有限,面对万字级长文档拆解、多步骤智能体链式调度、大型工程代码重构等高难度任务时,极易出现逻辑断层、信息幻觉、步骤遗漏,无法支撑自动化数字员工、行业数据分析等深度业务;其二,线上高端旗舰模型采用按量计费模式,批量内容生产、7×24小时智能体挂机场景下算力消耗不可控,中小开发者、小型工作室难以长期稳定调用,预算波动极大。
507 0
|
4月前
|
存储 人工智能 自然语言处理
阿里云盘企业版 CDE Agent 正式发布!企业网盘会思考、能办事,存储即智能
阿里云盘企业版推出CDE Agent,依托Qoder Cloud Agent实现网盘内文件智能处理与内容生成。文件存入即成“可对话、可执行”的智能资产,支持多模态检索、跨格式分析、自动总结与安全分享,全程数据不出域、权限原生继承、操作全程审计,让网盘升级为安全合规的AI智能工作空间。
760 0
|
4月前
|
前端开发 测试技术 API
聊聊 Swagger/Postman/Apifox 的真实选型
本文深度对比Swagger、Postman与Apifox三款主流API工具,从定位本质出发,围绕文档一致性、调试能力、Mock效率、自动化测试及团队协作五大维度展开横向分析,并结合Python项目实战演示接入流程,为不同规模团队提供清晰、可落地的选型指南。(239字)
531 0
|
5月前
|
机器学习/深度学习 人工智能 算法
王耀恒:当培训变成传销,GEO就成了新的“智商税”
GEO培训讲师王耀恒揭露“伪GEO”乱象:以AI排名为名,行传销之实——卖代理权、洗脑招商、批量发稿投毒。真相是:真GEO不靠系统,而靠优质内容、独特数据与用户意图匹配。拒绝捷径,回归价值。(239字)
|
5月前
|
安全 BI 数据安全/隐私保护
Quick BI使用案例27:如何通过“自定义角色+独立授权”实现数据集问数权限的精准控制
本文通过“自定义组织角色+数据集独立授权”,让组织中普通用户A在群空间中仅对其有编辑权的数据集进行问数及配置,严格遵循最小权限原则,兼顾安全与效率。