首页 > 其他分享 >1267:【例9.11】01背包问题(从二维优化一维dp问题)

1267:【例9.11】01背包问题(从二维优化一维dp问题)

时间:2024-09-29 17:21:33浏览次数:11  
标签:遍历 int 1267 9.11 01 一维 物品 背包 dp

代码如下:

# include <iostream>
using namespace std;
int dp[10010], w[200], c[200];
int main()
{
	int m, n;
	cin>>m>>n;
	for(int i = 1; i <= n; i++)
	{
		cin>>w[i]>>c[i];
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = m; j >= w[i]; j--)
		{
			dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
		}
	}
	cout<<dp[m]<<endl;
	return 0;
}

这个代码能够优化到一维的数组,因为你可以这样理解,就是二维数组的每一行,全部把他放到一行里面去,也就是下面这个转换

 至于说一维dp问题,里面有很许多要注意的细节,与二维dp做比较,有很多问题,以下我一一列举下来,我也一一给出答案。

第一个问题:

问:为什么二维背包的遍历顺序背包或者物品重量都可以调换,而优化后一维dp的遍历顺序一定要先是物品然后才是背包?

答案:因为二维背包先遍历物品或者先遍历背包都是可以的,因为后面的结果都是基于行和列来算出的结果。一维dp只能先遍历物品,在遍历背包,因为你不能动每一列的顺序,只能把行往后面加,然后变成了一维dp,然后你遍历的每一个数组,也就是原先每一行的背包容量,所以只能先遍历物品,然后遍历背包。

 第二个问题:

问:为什么一维dp遍历背包顺序必须是从后往前遍历,而不是从前往后遍历

假设一组数据

背包容量为4

物品1  重量1 价值15

物品2  重量3 价值20

物品3  重量4 价值30

答:因为我们可以用枚举法,当我们从前往后遍历的话,dp[j] = max(dp[j], dp[j - w[i]] + c[i]);当背包容量为0时,那就是不能放,当背包为1时,最大的就是15,当背包为2时,这个时候还能去放一个物品1,这个时候就重复了,因为物品1只有1个,所以就互相矛盾,只能从后往前遍历了。

第三个问题:

问:为什么遍历顺序是从1开始的?

答:这个也很好理解,因为当0的时候,我们其实就可以默认为没有背包,所以就得从1开始。

总结:其实01背包是最基本的背包问题,我们一定要吃透这个背包问题,才能往后走的更远,打好基础,才能把船行驶的更远。就我而言,我比较笨,我这个问题,我反复学了不下3遍,现在才学好关于这个01背包问题。

标签:遍历,int,1267,9.11,01,一维,物品,背包,dp
From: https://blog.csdn.net/Ricky_youngone/article/details/142455725

相关文章

  • 【问题解决】win10日志错误:创建 TLS 客户端凭据时发生致命错误。 内部错误状态为 1001
    背景最近win10死机了一次,查看事件管理器发现有大量的报错:“创建TLS客户端凭据时发生致命错误。内部错误状态为10013”,如图:解决win键搜索internet选项确定。原因参考错误:“创建TLS客户端凭据时发生致命错误。内部错误状态为10013”的说法是win10对TLSv3.0兼容性......
  • 干货|CNAS-CL01设备部分解读,透彻掌握软件测试实验室设备关键点
    CNAS-CL01《检测和校准实验室能力认可准则》是软件测试实验室建立符合CNAS标准的质量管理体系必须要贯彻的一部准则,分为五大核心部分:通用要求、结构要求、资源要求、过程要求和管理体系要求。前面的文章中我们为大家分享了通用要求部分、结构要求部分以及资源要求中的人员部分,......
  • CF2019D Speedbreaker
    题意Link一个数轴上有\(1,2,\dots,n\)共\(n\)个点。第\(1\)秒时,你将从其中一个点开始染色,称为初始点,之后第\(2,3,\dots,n\)秒,你每秒可以将一个被染色的点左边或右边的点染色。每个点有一个时间限制,必须要在\(a_i\)秒前(包含第\(a_i\)秒)被染色,问有多少个初始点可以将......
  • CF2019D. Speedbreaker 题解
    介绍一种另解,以下称“征服”为“拓展”。对于这些需要拓展,且拓展的时间有上界的题,我们通常都会有一个trick。那就是对于一个点\(x\),用它可以拓展到的点\(y\)的时间上界把\(x\)的时间上界继续缩小。用到这种trick的题有P9755[CSP-S2023]种树、[ABC304Ex]ConstrainedTop......
  • 2024-2025-1 20241301 《计算机基础与程序设计》第4周学习总结
    这个作业属于哪个课程<[2024-2025-1-计算机基础与程序设计](https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP)>这个作业要求在哪里<2024-2025-1计算机基础与程序设计第一周作业>这个作业的目标<总结一周内的学习内容,巩固所学,加深对计算机学科的理解,提升思考能......
  • 打卡信奥刷题(800)用Scratch图形化工具信奥P8241[普及组/提高] [COCI2013-2014#3] RIJE
    [COCI2013-2014#3]RIJEČI题目描述一天,Mirko发现了一个非常大的屏幕,这个屏幕上一开始只有一个字母A\texttt{A}A。Mirko在这个屏幕旁边找到了一个按钮。当他按一次时......
  • P1955 [NOI2015] 程序自动分析(并查集)
    相等放并查集里,不等直接判断#include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefv......
  • CF2019C Cards Partition
    涉及知识点:鸽巢原理,贪心前言唐诗题,赛时都已经想到了所有性质,以为要从数学方法上求解,却没想到就是个纯贪心题……题意Link给你一堆数,\(1,2,3,\dots,n\),分别有\(a[1],a[2],a[3],\dots,a[n]\)个,你还可以添加不超过\(k\)个数(当然这些数得是\(1\simn\)中的整数),你需要将它们......
  • day01-elasticstack-all
    一.elasitcstack概述什么是ElasticStack?所谓的ElasticStack别名为elkstack。ELK指的是三个技术栈: -ElasticSearch,简称:es 数据库,应用场景为数据的快速检索。 但凡和搜索框相关的,都会用ES进行数据的查询。 -Logstash: 采集数据,日志聚合,处理数据,将数据写入到ES......
  • 全国省、市、县(区)土地利用类型及面积面板数据(2019-2022年)
    土地利用类型是根据土地利用方式和地域差异对土地资源单元进行划分的基本土地地域单元。2019年-2022年全国省、市、县(区)土地利用类型及面积面板数据_土地利用类型数据下载资源-CSDN文库https://download.csdn.net/download/2401_84585615/89466102 土地利用类别在生产和建......