01背包【B站正月点灯笼讲解版和yxc版】

2024-03-04 16:18
文章标签 讲解 01 背包 灯笼 yxc 正月

本文主要是介绍01背包【B站正月点灯笼讲解版和yxc版】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

yxc版

题目链接
从1开始,f[i][j]表示前i个物品占用j空间的最大价值。
v表示第i件物品的体积,p表示第i件物品的价值。
f[i][j]可以有两个转移来源。

  • 不选第i个物品:f[i][j] = f[i-1][j]
  • 选第i个物品:f[i][j] = f[i-1][j - v[i]] + p[i]

时间复杂度 O ( n m ) O(nm) O(nm)

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

核心代码

使用滚动数组将二维的数据优化为一维,降低了空间复杂度。
直接套模板

//物品数量是5 最大容量是 20 
int d[21]={0}; 
void knapsack2(){for(int i = 1; i <= 5; i++){for(int c = 20; c >= w[i]; c--){d[c] = max(d[c], d[c - w[i]] + v[i]);}}
}

完整版

根据B站灯神视频讲解改写而成

#include<iostream>
using namespace std;
int dp[6][21] = {0}; //dp[i][c]表示前i件物品恰好装入容量为c的背包所能获得的最大价值 
int d[21]={0}; 
int w[] = {0, 2, 3, 4, 5, 9};//读入的时候做个偏移 
int v[] = {0, 3, 4, 5, 8, 10};
//物品数量是5 最大容量是 20 
void knapsack(){for(int i = 1; i <= 5; i++){for(int c = 1; c <= 20; c++){ //从1开始 if(c >= w[i]) dp[i][c] = max(dp[i-1][c], dp[i-1][c - w[i]] + v[i]);//放与不放 else //第i件物品太重了 dp[i][c] = dp[i - 1][c];}}
}
//物品数量是5 最大容量是 20 
void knapsack2(){for(int i = 1; i <= 5; i++){for(int c = 20; c >= w[i]; c--){d[c] = max(d[c], d[c - w[i]] + v[i]);}}
}int main(){knapsack2();for(int i = 0; i <= 20; i++) cout<<d[i]<<" ";	return 0;
} 

这篇关于01背包【B站正月点灯笼讲解版和yxc版】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/773730

相关文章

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Java集合中的List超详细讲解

《Java集合中的List超详细讲解》本文详细介绍了Java集合框架中的List接口,包括其在集合中的位置、继承体系、常用操作和代码示例,以及不同实现类(如ArrayList、LinkedList和V... 目录一,List的继承体系二,List的常用操作及代码示例1,创建List实例2,增加元素3,访问元

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip?2. 什么是 -i 参数?二、国内镜像源的选择三、如何

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

Redis的Zset类型及相关命令详细讲解

《Redis的Zset类型及相关命令详细讲解》:本文主要介绍Redis的Zset类型及相关命令的相关资料,有序集合Zset是一种Redis数据结构,它类似于集合Set,但每个元素都有一个关联的分数... 目录Zset简介ZADDZCARDZCOUNTZRANGEZREVRANGEZRANGEBYSCOREZ

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操

poj2576(二维背包)

题意:n个人分成两组,两组人数只差小于1 , 并且体重只差最小 对于人数要求恰好装满,对于体重要求尽量多,一开始没做出来,看了下解题,按照自己的感觉写,然后a了 状态转移方程:dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数,j表示背包容量,k表示输入的体重的 代码如下: #include<iostream>#include<

hdu2159(二维背包)

这是我的第一道二维背包题,没想到自己一下子就A了,但是代码写的比较乱,下面的代码是我有重新修改的 状态转移:dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示,打了i个怪物,消耗j的耐力值,所得到的最大经验值 代码如下: #include<iostream>#include<algorithm>#include<

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物,m个人,每个人的魔法消耗和魔法伤害不同,求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map