首页 > 其他分享 >背包模型

背包模型

时间：2023-09-10 22:02:03浏览次数：37  
标签：背包 int max 模型 物品 include 优化

状态表示是化零为整的过程，将一些零碎的数据化为一个集合 状态计算是化整为零的过程，需要将上述得到的集合分解为具体的数据才能进行计算

01背包

问题描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。 第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

特征：每样物品最多只能选择一次

问题分析

$f(i, j)$表示从前i个物品中选，总体积不大于j的选法的最大价值 $f(i, j) = max(f(i - 1, j), f(i - 1)(j - v_i) + w_i)$

朴素版代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; ++ i)
        for (int j = 0; j <= m; ++ j)
        {
            f[i][j] = f[i - 1][j]; // 未选择第i个物品
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); // 选择第i个物品，但前提是剩余容量体积大于等于第i个物品的体积
        }
    
    cout << f[n][m] << endl;
    return 0;
}

优化方法

  1. 将二维变为一维，f[i][j] = f[i - 1][j]变为f[j] = f[j]，由于是恒等式，所以直接删除即可；
  2. if (j >= v[i])判断直接放进循环即可，for (int j = 0; j <= m; ++ j) 变为 for (int j = v[i]; j <= m; ++ j)
  3. 但是这样做之后，f[j] = max(f[j], f[j - v[i]] + w[i]);并不等价于f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);，而是等价于f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);， 因为按照j从小到大的顺序，更新f[j]的f[j - v[i]]已经被更新了，变成了f[i][j - v[i]]，并不是我们想要的f[i - 1][j - v[i]]。 所以j的遍历顺序应该变为从大到小的for (int j = m; j >= v[i]; -- j)，这样才可以保证更新f[j]的是上一层的f[j - v[i]]

优化版代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        cin >> v[i] >> w[i];
    
    // 初始化需要初始f[0][0~m]均为0，由于全局数组默认为0，所以省去了初始化
    for (int i = 1; i <= n; ++ i)
        // for (int j = v[i]; j <= m; ++ j) // 这样做不行的原因在于更新f[j]的f[j - v[i]]已经被修改了，实际上为f[i][j - v[i]]了,而非f[i - 1][j - v[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;
}

完全背包

问题描述

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有无限件可用。 第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

特征：每样物品可选择任意次

问题分析

$f(i, j)$表示从前i个物品中选，总体积不大于j的选法的最大价值 $f(i, j) = max(f(i - 1)(j - k * v_i) + k * w_i) (0 \leq k \leq \frac{j}{v_i})$

朴素版代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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

优化方法

按照图片中的方法我们可以得到一次优化代码 按照01背包的优化方法，我们可以得到二次优化代码 但是需要注意的是，j的遍历顺序是从小到大的，因为更新f[i][j]的是f[i][j - v],而非01背包中的f[i - 1][j - v]，也就是我们需要的f[j - v]是这一层已经更新过的，而非上一层的

一次优化代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        cin >> v[i] >> w[i];
        
    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][j], f[i][j - v[i]] + w[i]);
        }
    
    cout << f[n][m] << endl;
    
    return 0;
}

二次优化代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        cin >> v[i] >> w[i];
        
    for (int i = 1; i <= n; ++ i)
        for (int j = v[i]; j <= m; ++ j) // 注意和01背包的区别
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m] << endl;
    
    return 0;
}

例题

  1. 整数划分 : 代码实现

多重背包

问题描述

有 $N$ 种物品和一个容量是 $V$ 的背包。 第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

特征：每样物品都有固定数目

问题分析

$f(i, j)$表示从前i个物品中选，总体积不大于j的选法的最大价值 $f(i, j) = max(f(i - 1)(j - k * v_i) + k * w_i) (0 \leq k \leq min(s_i, \frac{j}{v_i}))$

朴素版代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    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 j = 0; j <= m; ++ j)
            for (int k = 0; k <= s[i] && k * v[i] <= j; ++ k)
                f[i][j] = max(f[i][j], f[i -1][j - k * v[i]] + k * w[i]);
    
    cout << f[n][m] << endl;
    return 0;
}

优化方法

完全背包优化方法的不可行性 多重背包问题与完全背包问题在问题分析和朴素版代码实现上都非常类似，所以第一感觉是按照完全背包问题的优化方法进行优化，但实际并不可行，以下对其不可行性进行论述 首先考虑按照完全背包的优化方法，红色框的两部分个数是相等的，都是从j-v开始到kv大于j结束，保证这的前提是完全背包问题中每个物品均可选择任意件

但是在多重背包问题中，由于物品数量是固定的，所以下图中两橙色框部分并不一定相等，如果在k(k <= s)之前kv已经>=j了，那么2式子中的绿色部分实际并不存在，那么按照完全背包的优化方法就是可行的，但是我们并不能保证这个前提。对于2式，假设绿色部分是存在的，并且已知橙色和绿色部分的最大值，因为除绿色部分外可能包含与绿色部分相等的成分，所以我们无法求出除绿色部分外的最大值，所以按照完全背包的方法是行不通的。综上所述，按照完全背包优化多重背包虽然存在可能性，但并非100%，所以不能按照之前的方法了。

二进制优化 注意到最内层的循环for (int k = 0; k <= s[i] && k * v[i] <= j; ++ k)，我们的目的是讨论第i种物品应选择几个。如果将这第i种物品的s个一一排列开来，我们顺序遍历，对每个物品我们都需要考虑选择或是不选择，这样做的结果是TLE。那么考虑有没有更快的方法来讨论物品应选择的个数，易知，任意一个数都可以根据二进制进行表示，所以我们将这s个物品按照二进制进行拆分，分为1个、2个、4个、8个...，将他们分别看为独立的物品，考虑每个物品是否选择就可以快速地讨论第i种物品应选择几个。根据描述可知，当拆分之后，问题就转化为了一个01背包问题。 可以看出，上述的方法主要是对朴素做法中的最内层循环进行优化，复杂度由$O(nvs)$优化为$O(nvlog(s))$

优化版代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;
    
    int cnt = 0;
    for (int i = 1; i <= n; ++ i)
    {
        int a, b, s;
        cin >> a >> b >> s;
        
        // 对每一组数据根据二进制将总个数进行划分
        int k = 1;
        while (k <= s)
        {
            ++ cnt;
            v[cnt] = k * a;
            w[cnt] = k * b;
            s -= k;
            k <<= 1;
        }
        if (s)
        {
            ++ cnt;
            v[cnt] = s * a;
            w[cnt] = s * b;
        }
    }
    
    n = cnt;
    
    // 到此问题已经转化为了01背包问题
    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;
}

分组背包

问题描述

有 N 组物品和一个容量是 V 的背包。 每组物品有若干个，同一组内的物品最多只能选一个。 每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。 求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。 输出最大价值。

特征：有多组物品，每组物品中只能选择一个

问题分析

$f(i, j)$表示从前i组物品中选，总体积不大于j的选法的最大价值 $f(i, j) = max(f(i - 1)(j - v[i][k]) + w[i][k]) (0 \leq k \leq s[i])$ 上式中$v[i][k]$表示第i组第k个物品的体积，w表示相同物品的价值 在第i组中的物品中任意选择一个(也可能不选)，找到其中的最大价值

朴素版代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; ++ j)
            cin >> v[i][j] >> w[i][j];
    }
    
    for (int i = 1; i <= n; ++ i)
        for (int j = 0; j <= m; ++ j)
            for (int k = 0; k <= s[i]; ++ k) // 考虑选择第i组中的哪个物品
                if (j >= v[i][k])
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
    
    cout << f[n][m] << endl;
    
    return 0;
}

优化方法

按照01背包的优化方法即可。注意j的遍历顺序，原因此前讲过，这里不再赘述

优化版代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; ++ j)
            cin >> v[i][j] >> w[i][j];
    }
    
    for (int i = 1; i <= n; ++ i)
        for (int j = m; j >= 0; -- j) // 注意这里的顺序
            for (int k = 0; k <= s[i]; ++ k) // 考虑选择第i组中的哪个物品
                if (j >= v[i][k])
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    
    cout << f[m] << endl;
    
    return 0;
}

标签：背包,int,max,模型,物品,include,优化
From： https://blog.51cto.com/u_14882565/7428444

相关文章

  • 浪潮信息“互联网+AIGC”巡展深圳站：湾区共话 大模型智算之道
    近日，浪潮信息新产品“互联网+AIGC”行业巡展在深圳举行。本次巡展以“智算开新局·创新机”为主题，来自华南理工大学、网易伏羲、腾讯云、浪潮信息等高校、知名企业、研究机构的产学研专家、互联网行业大咖再度聚首，围绕大模型发展的机遇与挑战，从技术、应用和产业等多个角度进行了精......
  • 2023.36 腾讯混元大模型
    9月7日，在2023腾讯全球数字生态大会上，腾讯混元大模型正式亮相。腾讯集团副总裁蒋杰介绍，混元大模型参数量超千亿，具备多轮对话能力，内容创作能力，逻辑推理能力，搜索增强和知识图谱。训练数据更新至今年7月份，未来会不断更新迭代。目前，腾讯已有超过50个自有产品和业务接入混元大模型测试。......
  • 06-MVVM模型
    每个Vue应用都是通过用 Vue 函数创建一个新的 Vue实例开始的：constvm=newVue({//选项})Vue的设计虽然没有完全遵循MVVM模型，但是也受到了它的启发。因此在文档中经常会使用 vm (ViewModel的缩写)这个变量名表示Vue实例。 MVVM模型M：模型（Mdel），对应Vue的......
  • 系统熵增是怎么产生的？————数据对象模型里添加属性欠思考
    熵增定律指出，在没有外力作用下的封闭系统中，熵（或混乱度）总是增加的。就是说，任何封闭系统中、在没有外力作用下，都会陷入混乱。屋子不收拾会变乱；人不自律会懒散；生活不规律或无节制，人就会出现健康问题；同样，对于我们的信息系统，一旦缺乏规范和管控，就会越来越难于迭代和维护。这些例子......
  • 【Qt6】列表模型——抽象基类
    列表模型（ItemModel），老周没有翻译为“项目模型”，因为Project和Item都可以翻译为“项目”，容易出现歧义。干脆叫列表模型。这个模型也确实是为数据列表准备的，它以MVC的概念为基础，在原始数据和用户界面视图之间搭建桥梁，使两者可以传递数据（提取、修改）。Qt里面使用列表控制比较......
  • JVM内存模型，JVM、JRE、JDK之间的关系，Java程序是如何执行的
    一、什么是JVMJVM是JavaVirtualMachine（Java虚拟机）的简称，是一个虚构出来的计算机，通过在实际的计算机上仿真模拟各种计算机功能来实现的。JVM屏蔽了与具体操作系统平台相关的信息，Java程序只需生成在Java虚拟机上运行的字节码，就可以在多种平台上不加修改的运行。JVM在执行字节码时，实......
  • Model关联模型，一对一，一对多，多对多
    一、一对一关系1、我们在models中创建一个新的模型,叫做StudentInfo点击查看代码classStudentInfo(BaseModel):"""学生信息附加表"""address=models.CharField(max_length=255,verbose_name="家庭地址")#当设置字段为外键时,ORM会自动根据当前外键属性名拼......
  • IDEFICS 简介: 最先进视觉语言模型的开源复现
    引言CodeLlama是为代码类任务而生的一组最先进的、开放的Llama2模型，我们很高兴能将其集成入HuggingFace生态系统！CodeLlama使用与Llama2相同的社区许可证，且可商用。今天，我们很高兴能发布HuggingFace对CodeLlama的全面支持,包括:Hub上的模型支持，包括模型......
  • Meta推出像素级动作追踪模型，简易版在线可玩 | GitHub 1.4K星
    前言 视频动作跟踪，已经精确到了每个像素！本文转载自量子位仅用于学术分享，若侵权请联系删除欢迎关注公众号CV技术指南，专注于计算机视觉的技术总结、最新技术跟踪、经典论文解读、CV招聘信息。CV各大方向专栏与各个部署框架最全教程整理【CV技术指南】CV全栈指导班、基础入门班......
  • css-盒子模型
    盒子模型1.是什么 2.边框边框的粗细边框的样式边框的颜色因为容易很丑~-~这里用结构伪类选择器:——本意为找div父类的子类中第一个为input的，但是有错，实际上是div的后代选择器如果去掉input,只会框第一个div,找div父类的子类中第一个孩子3.外边距两......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99