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

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

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