算法学习之动态规划DP——背包问题

一、01背包问题

（一）题目

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第i件物品的体积和价值。

输出格式

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

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

（二 ）题解

 【一】 二维动态规划

（1）状态f[i][j]定义：前 i 个物品，背包容量 j下的最优解（最大价值）：

    当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 N

件物品，则需要 N 次决 策，每一次对第 i件物品的决策，状态f[i][j]不断由之前的状态更新而来。

（2）当前背包容量不够（j < v[i]），没得选，因此前 i个物品最优解即为前 i−1个物品最优解：

    对应代码：f[i][j] = f[i - 1][j]。

（3）当前背包容量够，可以选，因此需要决策选与不选第i个物品：

    选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
    不选：f[i][j] = f[i - 1][j] 。
    我们的决策是如何取到最大价值，因此以上两种情况取 max() 。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1010;

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

int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) scanf("%d%d", &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-1][j-v[i]]+w[i]);
        }
    }
    printf("%d", f[n][m]);
    return 0;
}
【二】优化：状态压缩（二维变一维）

将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。

为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

（1）状态f[j]定义：N件物品，背包容量j下的最优解。

（2）注意枚举背包容量j必须从m开始。

为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

例如，一维状态第i轮对体积为 3的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]正确应该f[i-1][4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时，我们求f[7]同样由f[4]更新，但由于是逆序，这里的f[4]还没有在第i轮计算，所以此时实际计算的f[4]仍然是f[i - 1][4]。

简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] 。

tips：若通过减少维数来进行状态压缩，要注意是否有一维循环需要逆序来保证更新所用到的状态没有被污染。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1010;

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

int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) scanf("%d%d", &v[i], &w[i]);
    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]);
        }
    }
    printf("%d", f[m]);
    return 0;
}

二、完全背包

（一）题目

有 N 种物品和一个容量是V的背包，每种物品都有无限件可用。

第i种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有N行，每行两个整数 vi,wi，用空格隔开，分别表示第i种物品的体积和价值。

输出格式

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

数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

（二）题解

闫式DP分析法

对应代码

二维DP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

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

int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) scanf("%d%d", &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]);        
        }
    }
    
    printf("%d", f[n][m]);
    return 0;
}

一维DP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

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

int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; ++ i){
        for(int j = 0; j <= m; ++ j){
            f[j] = f[j];  // 等价替换f[i][j] = f[i-1][j];
            if(j >= v[i]) f[j] = max(f[j], f[j-v[i]]+w[i]);  // 等价替换f[i][j] = max(f[i][j], f[i][j-v[i]]+w[i])
            // 总结：替换的是f[i-1][...]还是f[i][...]取决于在该i层循环中，等号右边的数组中出现的下标有没有更新过，若更新过就是f[i][...]， 反之则是f[i-1][...]
        }
    }
    
    printf("%d", f[m]);
    return 0;
}

简化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

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

int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; ++ i){
        for(int j = v[i]; j <= m; ++ j){
           f[j] = max(f[j], f[j-v[i]]+w[i]);      
        }
    }
    
    printf("%d", f[m]);
    return 0;
}

 三、多重背包问题

（一）题目

有N 种物品和一个容量是V的背包。

第i种物品最多有 si 件，每件体积是vi，价值是wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第i种物品的体积、价值和数量。

输出格式

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

数据范围

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

输入样例

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

输出样例

10

 

（二）题解

思路：可以将多重背包问题转化为01背包问题。

1.朴素的转化思路

可以直接转化为有s[1]+s[2]+...s[n]个物品，背包容量为V的01背包问题。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;

int n, m;

int f[N];

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i){
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        for(int j = m; j >= 0; -- j){
            for(int k = 1; k <= s; ++ k){
                if(j >= k*v) f[j] = max(f[j], f[j-k*v]+k*w);
            }
        }
    }
    
    printf("%d", f[m]);
    return 0;
}

时间复杂度分析

O（N*V*Si）（大约为10^9）在本题目的数据范围限制下会超时。

2.优化

上述做法是将Si拆成了Si个1。

tips:

能否将Si拆成小于Si个数，使这些数可以表示1~Si之间的所有数？

答案是可以的。

（结论）其实只需要将Si拆成log(Si)（上取整）个数即可。这Si个数分别为2^0, 2^1, 2^2……2^log(Si)。

注意：对于Si恰好等于以2为底的指数减1倍时，是恰好符合题意的。而其他值在经过log(Si)（上取整）个数相加后仍会小于Si，只需要将剩余的这部分单独拿出来即可。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 2010;

int n, m;

int f[N];

struct good{
    int v, w;
};

int main(){
    vector<good> goods;
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++ i){
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        for(int k = 1; k <= s; k *= 2){
            s -= k;
            goods.push_back({k*v, k*w});
        }
        if(s > 0) goods.push_back({s*v, s*w});
    }
    
    for(auto item: goods){
        for(int j = m; j >= item.v; -- j){
            f[j] = max(f[j], f[j-item.v]+item.w);
        }
    }
    
    printf("%d", f[m]);
    return 0;
}

四、分组背包问题

（一）题目

有 N 组物品和一个容量是V的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有N组数据：

  • 每组数据第一行有一个整数 S，表示第i个物品组的物品数量；
  • 每组数据接下来有 S行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第j个物品的体积和价值；

输出格式

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

数据范围

0<N,V≤100

0<Si≤100
0<vij,wij≤100

输入样例

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

输出样例

8

（二）题解

注意：多重背包问题是分组背包问题的一个特殊情况。

分组背包问题同样也是01背包问题的一个变种。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;

int n, m;

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

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++ i){
        int s;
        scanf("%d", &s);
        for(int j = 1; j <= s; ++ j) scanf("%d%d", &v[j], &w[j]);
        for(int j = m; j >= 0; -- j){
            for(int k = 1; k <= s; ++ k){
                if(j >= v[k]) f[j] = max(f[j], f[j-v[k]]+w[k]);
            }
        }
    }
    
    printf("%d", f[m]);
    return 0;
}

总结

01背包问题，多重背包问题，分组背包问题是同一大类背包问题。在i层循环中只能做一个选择（即选与不选）（对于多重背包和分组背包的选对应的是多种选择）。

而完全背包是另一大类问题。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/446405.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

前后端交互理解 简易表白墙（servlet）

前后端交互理解 简易表白墙（servlet）

前后端交互理解 简易表白墙&#xff08;servlet&#xff09; 文章目录 前后端交互理解 简易表白墙&#xff08;servlet&#xff09;后端核心内容前后端交互接口约定后端代码展示 上期介绍过 Servlet API &#xff0c;本篇文章目的是借助 servlet 做出一个完整的网站。在一个网站…
阅读更多...
51单片机基础篇系列-人人都能学会单片机

51单片机基础篇系列-人人都能学会单片机

&#x1f308;个人主页: 会编程的果子君 &#x1f4ab;个人格言:“成为自己未来的主人~” 什么是单片机 在一片集成电路芯片上集成计算机所有基 本部分&#xff08;中央处理器CPU、存储器RAM、ROM、 定时计数器T/C&#xff0c;输入输出接口IO、中断系 统&#xff09;都集成…
阅读更多...
【UVM_phase objection_2024.03.08

【UVM_phase objection_2024.03.08

phase 棕色&#xff1a;function phase 不消耗仿真时间 绿色&#xff1a;task phase 消耗仿真时间 run_phase与右边的phase并行执行&#xff0c;右边的phase&#xff08;run_time phase&#xff09;依次执行&#xff1a; List itemreset_phase对DUT进行复位&#xff0c;初始…
阅读更多...
Elastic Stack--07--JavaAPI----文档（新增 、修改 、 查询 、 删除）

Elastic Stack--07--JavaAPI----文档（新增 、修改 、 查询 、 删除）

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 JavaAPI-文档1.新增 Insert2.修改 Update3.查询 Get4.删除 Delete5.批量操作 BulkRequest批量新增批量删除 高级查询1.查询所有索引数据2.条件查询3.分页查询4.查询…
阅读更多...
代码随想录算法训练营Day39 || leetCode 762.不同路径 || 63. 不同路径 II

代码随想录算法训练营Day39 || leetCode 762.不同路径 || 63. 不同路径 II

62.不同路径 每一位的结果等于上方与左侧结果和 class Solution { public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector(n,0));for (int i 0; i < m; i) dp[i][0] 1;for (int j 0; j < n; j) dp[0][j] 1;for (int i 1; i < m; …
阅读更多...
基于raft的kvDB

基于raft的kvDB

1 raft共识算法 raft是强leader模型&#xff0c;通过选举leader来实现一致性&#xff0c;leader拥有完全的能力来管理复制日志。leader从客户端获取日志条目&#xff0c;复制到其他的服务器中&#xff0c;告诉他们什么时候应用这个日志到状态机是安全的。 leader这个角色简化…
阅读更多...
实现“ 字体逐渐展现 ”程序

实现“ 字体逐渐展现 ”程序

本期介绍&#x1f356; 主要介绍&#xff1a;如何实现在屏幕上从两边向中间逐渐打印字符串。 题目&#xff1a;编写字体逐渐展现程序&#xff0c;功能是&#xff1a;多个字符从两端向中逐渐间显现&#xff0c;直到全部显示为止。举个例子&#xff0c;要逐渐显示“hello world ”…
阅读更多...
MEMTO: Memory-guided Transformer for Multivariate Time Series Anomaly Detection

MEMTO: Memory-guided Transformer for Multivariate Time Series Anomaly Detection

目录 一、问题与思路1.1 现存问题1.2 解决思路 二、模型与方法2.1 模型概览2.2 Encoder and decoder2.3 门控存储器模块2.3.1 门控存储器更新阶段2.3.2 查询更新阶段2.3.3 损失函数2.3.4 初始化内存项2.3.5 异常评分2.3.6 阈值设定 三、实验与分析3.1 模型结果3.2 消融实验3.3 …
阅读更多...
宝塔一键迁移报错创建失败问题完美解决

宝塔一键迁移报错创建失败问题完美解决

很多站长朋友在使用宝塔面板迁移的时候总是出错&#xff0c;如图&#xff1a; 遇到这样的问题不要慌&#xff0c;我们已经完美处理&#xff0c;详细解决教程&#xff1a;宝塔一键迁移报错问题完美解决教程
阅读更多...
深入理解操作系统Operator System（2）

深入理解操作系统Operator System（2）

目录 操作系统对上的管理 系统调用接口 用户操作接口&#xff08;库函数&#xff09; 系统调用和库函数的概念 结构层次示意图 总结 为什么要有操作系统❓ 上次主要介绍了操作系统的"管理"和操作系统对下的管理。本篇主要是对上的管理。 操作系统对上的管理 …
阅读更多...
Linux智能网关结合Node-RED实现实时工业数据采集

Linux智能网关结合Node-RED实现实时工业数据采集

工业4.0的发展&#xff0c;物联网技术在制造业中的应用越来越广泛。其中&#xff0c;基于Linux系统的工业物联网智能网关因其开放性、稳定性和安全性而备受青睐。这类智能网关创新性地集成了开源工具Node-RED&#xff0c;为从各种工业设备&#xff08;如PLC&#xff09;中高效收…
阅读更多...
安装torch以及版本对应问题

安装torch以及版本对应问题

首先查看cuda版本&#xff1a;winR 输入&#xff1a;nvidia -smi 我的cuda版本12.2&#xff0c;安装的torch版本要小于12.2 我的pip/conda源都改成清华源了&#xff0c;torch2.0以上的版本截止到2024年3月10日也没有。 pytorch官网&#xff1a;https://pytorch.org/ 寻找匹配…
阅读更多...
关于比特币的AI对话

关于比特币的AI对话

【ChatGPT】 比特币源码开源吗&#xff1f; 是的&#xff0c;比特币的源码是开源的。比特币项目是在MIT许可证下发布的&#xff0c;这意味着任何人都可以查看、修改、贡献和分发代码。比特币的源码托管在GitHub上&#xff0c;可以通过下面的链接进行访问&#xff1a; https://g…
阅读更多...
注意！！墙裂推荐几个好用的实用小工具！一定会用到的！

注意！！墙裂推荐几个好用的实用小工具！一定会用到的！

前言 在开发的世界里&#xff0c;面对各种挑战和问题时&#xff0c;拥有一套合适的工具箱至关重要。这不仅能提升我们的工作效率&#xff0c;还能让复杂的任务变得简单&#xff0c;甚至在解决棘手问题的同时&#xff0c;还能让我们的心情略微舒畅。众所周知&#xff0c;有用的…
阅读更多...
【EtherCAT实践篇】九、EtherCAT增加变量示例：增加浮点数输入变量

【EtherCAT实践篇】九、EtherCAT增加变量示例：增加浮点数输入变量

目的&#xff1a;在EtherCAT开发板上IO程序基础上进行修改&#xff0c;将原来的16位整数型数据Analog input改为32位浮点数&#xff0c;基于STM32F405底板。 1、XML配置修改 1.1 更改数据类型 ETG1020基础数据中包括浮点数 REAL&#xff0c;可以直接使用浮点数。 这里在xml…
阅读更多...
MySQL索引+常见问题详解

MySQL索引+常见问题详解

网络上的讲述MySQL索引的文章太多了&#xff0c;我打算换个角度来说。我们尝试着从设计者的角度思考&#xff0c;索引为什么这么设计。 假如你是索引的设计者&#xff0c;你会如何设计索引。我们不妨以新华字典为例。如果我们要查询汉字爱是什么意思&#xff0c;我们有如下操作…
阅读更多...
【读书笔记】针对ICS的ATTCK矩阵详解（一）

【读书笔记】针对ICS的ATTCK矩阵详解（一）

Techniques - ICS | MITRE ATT&CKhttps://attack.mitre.org/techniques/ics/ 一、初始访问&#xff08;Initial Access&#xff09; 该阶段&#xff1a;攻击者正在尝试进入ICS环境。 初始访问包括攻击者可能用作入口向量&#xff0c;从而可以在 ICS 环境中获得初始立足点的…
阅读更多...
怎么在学习强国网上发布文章，学习强国投稿发稿方法途径，附学习强国多少钱价格明细表

怎么在学习强国网上发布文章，学习强国投稿发稿方法途径，附学习强国多少钱价格明细表

学习强国是一款受用户欢迎的学习软件&#xff0c;许多人希望在其平台上发布自己的文章&#xff0c;以分享和传播自己的学习成果和心得体会。那么&#xff0c;怎么在学习强国网上发布文章呢&#xff1f;接下来&#xff0c;我们将介绍一些投稿发稿的方法和途径。 首先&#xff0c…
阅读更多...
PLC的FC与FB模块程序的功能解析

PLC的FC与FB模块程序的功能解析

前文讲了在西门子系列的PLC中四个程序模块的描述&#xff0c;从S7-1200PLC开始就有FC和FB程序块了&#xff0c;但在使用的时候&#xff0c;一些使用者还是不好理解&#xff0c;以至于不知道该如何选择。今天&#xff0c;我们就用大白话的方式给大家讲解FC与FB的功能。 1、FC与…
阅读更多...
Python打印Linux系统中最常用的linux命令之示例

Python打印Linux系统中最常用的linux命令之示例

一、Linux中的~/.bash_history文件说明&#xff1a; 该文件保存了linux系统中运行过的命令的历史。使用该文件来获取命令的列表&#xff0c;并统计命令的执行次数。统计时&#xff0c;只统计命令的名称&#xff0c;以不同参数调用相同的命令也视为同一命令。 二、示例代码&am…
阅读更多...
最新文章

Copyright @ 2022~2023