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

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

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



目录
相关文章
|
机器学习/深度学习 人工智能 网络架构
Transformer原理解析——一种Open AI和DeepMind都在用的神经网络架构
Transformer模型是一种日益流行的神经网络结构。它最近被OpenAI用于他们的语言模型中。与此同时,近期也被DeepMind用于它们的程序“星际争霸”中击败了一名顶级职业星际玩家。 Transformer模型的开发是为了解决序列转换及神经机器翻译问题。
9029 0
|
机器学习/深度学习 人工智能 自动驾驶
人工智能的伦理困境:当机器学习遇见道德选择
在人工智能飞速发展的今天,技术的进步不仅带来了便利和效率,也引发了一系列伦理问题。本文将探讨AI在决策过程中面临的伦理挑战,以及如何通过设计、立法和教育等手段来解决这些问题。
280 3
|
供应链 Kubernetes 安全
谈谈我对云原生与软件供应链安全的思考
阿里云容器服务 ACK、容器镜像服务 ACR 在容器安全领域有着深厚的投入。在信通院首次 “云原生安全成熟度”评估中,阿里云取得了国内唯一全域最高等级认证。我们也在和 OCI, Sigstore 等社区合作,持续为企业客户提供更加可信赖、更加易用的软件供应链安全能力。
1217 108
谈谈我对云原生与软件供应链安全的思考
|
前端开发 Unix Windows
SAP打印配置
SAP打印机原理、打印配置及打印操作
SAP打印配置
|
敏捷开发 前端开发 项目管理
在YesDev研发协同工具,项目协作 All In One
值得注意的是,YesDev中所定义和提倡的项目,是指在一定时间周期内完成的有限需求、任务和问题的集合,对应敏捷开发中的一次迭代或Scrumn的一个Sprint。
|
NoSQL Redis 数据安全/隐私保护
redis:(error) NOAUTH Authentication required
redis:(error) NOAUTH Authentication required
297 0
|
缓存 编解码 API
淘票票 iOS 客户端:视频本地代理与缓存方案
提高客户端视频起播速度一直是比较关键的优化点。如何提高起播速度?除了通过优化网络、提高服务器带宽、优化视频文件码率帧率等常规方案外,还可以从哪些方面进行优化呢?一起来看看吧!
淘票票 iOS 客户端:视频本地代理与缓存方案
|
监控 前端开发 Cloud Native
第十六届 D2 前端技术论坛完成 6 大专场 21 个话题集结,快来划重点,你一定会有所收获!
一年一度的前端盛会D2前端技术论坛就要来啦,话题集结完成,快来报名学习吧!
1783 0
第十六届 D2 前端技术论坛完成 6 大专场 21 个话题集结,快来划重点,你一定会有所收获!
|
存储 运维 监控
一文详尽如何破解车联网数据采集存储难题
Lindorm车联网数据存储解决方案
3398 0
一文详尽如何破解车联网数据采集存储难题
|
Java API PHP
阿里云人脸识别综述
本文主要对阿里云人脸识别功能及开发语言的实现做一个概述,为用户使用提供参考。
4930 0