一本通 1267:【例9.11】01背包问题(详细代码+严谨思路+清晰图片) C++

这篇具有很好参考价值的文章主要介绍了一本通 1267:【例9.11】01背包问题(详细代码+严谨思路+清晰图片) C++。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1267:【例9.11】01背包问题,一本通,c++,动态规划,深度优先

经典01背包问题

这里给你 种方法!!


目录

DFS

思路:

代码:

DFS+记忆化

思路:

代码:

动态规划

思路:

代码:


DFS

时间复杂度 :O(2^n)

思路:

DFS求出所有选法,再用ans记录价格最大值

由于此题数据量较小(其实2^30=1073741824,这种做法是过不了的,是题目数据比较水^_^)

代码:

//【例9.11】01背包问题
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35;

int n, m, ans;//n 容量    m 物品
int w[N], v[N]; //w 第i件物品的重量(代价)   v 第i件物品的价值

//idx 物品编号   resw 背包剩余容量   sumv 当前决策下的总价值
void dfs(int idx, int resw, int sumv) {
	if (idx == n + 1) {
		ans = max(ans, sumv);
		return ;
	}

	//不选
	dfs(idx + 1, resw, sumv);
	//选
	if (resw >= w[idx])
		dfs(idx + 1, resw - w[idx], sumv + v[idx]);
}

int main() {
	cin >> m >> n;

	for (int i = 1; i <= n; i ++)
		cin >> w[i] >> v[i];

	dfs(1, m, 0);

	cout << ans;
	return 0;
}
/*
【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12
*/

如果在考试遇到这种01背包题目DFS是肯定拿不了满分的


DFS+记忆化

时间复杂度:O(nm)

针对上一个做法 纯·DFS 有可能会超时的情况我们推出了加上记忆化的版本

思路:

我们分析一下为什么 纯·DFS 做法会超时

我们用一个小样例自己推一下

1267:【例9.11】01背包问题,一本通,c++,动态规划,深度优先

 先不管答案是什么,我们发现dfs(1, 5)出现了多次

如果样例再大一点就会有很多重复子问题

重复子问题 ?想到什么了?对了,用记忆化存储状态!

只要在上一种方法的代码加上一个二维dp数组存储状态就能起到优化时间复杂度的作用

dp[i][j] 代表 用前i件物品来装容量为j的背包所能得到的最大价值

代码:

//【例9.11】01背包问题
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35, M = 205;

int n, m;//n 容量    m 物品
int w[N], v[N]; //w 第i件物品的重量(代价)   v 第i件物品的价值

/*
idx 物品编号   resw 背包剩余容量
	如果
	第i件物品不选
		dfs(i, j) = dfs(i - 1, j)
	第i件物品选
		dfs(i, j) = dfs(i - 1, j - w[i]) + v[i]
*/
int dp[N][M];
int dfs(int idx, int resw) {
	//用前i件物品来装容量为j的背包所能得到的最大价值
	if (!idx)
		return 0;
	if (dp[idx][resw] != -1)
		return dp[idx][resw];

	//不选
	int maxn = dfs(idx - 1, resw);
	//选
	if (resw >= w[idx])
		maxn = max(maxn, dfs(idx - 1, resw - w[idx]) + v[idx]);

	return dp[idx][resw] = maxn;
}

int main() {
	cin >> m >> n;

	for (int i = 1; i <= n; i ++)
		cin >> w[i] >> v[i];

	memset(dp, -1, sizeof dp);

	cout << dfs(n, m);
	return 0;
}
/*
【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12
*/

动态规划

时间复杂度:O(nm)

思路:

其实也就是把 DFS+记忆化 改成递推形式,在上一种方法的代码里也已经透露了状态转移方程

第i件物品不选
	dp[i, j] = dp[i - 1, j]
第i件物品选
	dp[i, j] = dp[i - 1, j - w[i]] + v[i]

代码:

//【例9.11】01背包问题   O(nm)
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35, M = 205;

int n, m;//n 容量    m 物品
int w[N], v[N]; //w 第i件物品的重量(代价)   v 第i件物品的价值
int dp[N][M];

int main() {
	cin >> m >> n;

	for (int i = 1; i <= n; i ++)
		cin >> w[i] >> v[i];

	/*
	dp[i, j] 用前i件物品来装容量为j的背包所能得到的最大价值
	第i件物品不选
		dp[i, j] = dp[i - 1, j]
	第i件物品选
		dp[i, j] = dp[i - 1, j - w[i]] + v[i]
	*/
	for (int i = 1; i <= n; i ++) {
		for (int j = 0; j <= m; j ++) {
			dp[i][j] = dp[i - 1][j]; //不选
			if (j >= w[i]) //可选
				dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
	cout << dp[n][m];
	return 0;
}
/*
【输入样例】
10 4
2 1
3 3
4 5
7 9
【输出样例】
12
*/

代码可以拿走,请把赞留下

原题链接:信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)文章来源地址https://www.toymoban.com/news/detail-643174.html

到了这里,关于一本通 1267:【例9.11】01背包问题(详细代码+严谨思路+清晰图片) C++的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 01背包问题----动态规划 -----python代码、优化

    问题描述: 容量为C的背包选择装物品,有n个物品,它们有各自的体积wi和价值vi,如何让背包里装入的物品具有最大价值? 解题思路: 也就是n个物品选择装入背包,每个物品都有两种选择,是(1)或否(0), 建模:       xi表示当前第i个物品是否选择,xi取值为(0,1)

    2024年02月04日
    浏览(53)
  • 动态规划01背包问题-代码随想录-刷题笔记

    有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。 每件物品只能用一次 ,求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包 确定dp数组以及下标的含义 是使用二维数组,即 dp[i][j] 表示从下标为[0-i]的物品里任意取,

    2024年02月07日
    浏览(56)
  • 回溯法解01背包问题(最通俗易懂,附C++代码)

    01背包问题是算法中的经典问题,问题描述如下: 对于给定的N个物品,第i个物品的重量为Wi,价值为Vi,对于一个最多能装重量C的背包,应该如何选择放入包中的物品,使得包中物品的总价值最大? 回溯法的本质其实就是一种蛮力法,只是通过一定的方法可以使得蛮力法中

    2023年04月08日
    浏览(33)
  • 代码随想录 Day35 动态规划04 01背包问题和完全背包问题 LeetCode T416 分割等和子集

    说到背包问题大家都会想到使用动规的方式来求解,那么为什么用动规呢, dp数组代表什么呢 ? 初始化是什么 , 遍历方式又是什么 ,这篇文章笔者将详细讲解背包问题的经典例题0-1背包问题和完全背包问题的解题方式,希望能帮助到大家 有人一提到背包问题就只会使用动态规划来

    2024年02月06日
    浏览(71)
  • 动态规划:0-1背包、完全背包问题 | 详细原理解释 | 代码及优化(C++)

    目录 01背包 问题描述: 简单描述就是: 解析: 递推公式: dp数组的初始化: 遍历顺序: 图解: 实现代码: dp数组初始化: 遍历: 优化: 原理: 递推公式: 遍历顺序: 实现代码: 初始化: 遍历: 完全背包 问题描述: 解析: 实现代码:         01背包是在M件物品

    2024年02月11日
    浏览(34)
  • 背包九讲(超详细 :算法分析 + 问题分析 + 代码分析)

    特点:每个物品只能用一次,只能是选择或者不选择 题目链接 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 v i ,价值是 w i 。 求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。 输出最大价值。 输入格式

    2023年04月08日
    浏览(34)
  • 背包问题——01背包|完全背包

    目录 前言背包问题的历史  01背包  1、题目 2、暴力解01背包  Ⅰ、代码 3、动态规划解01背包 Ⅰ、二维dp数组解01背包 1)dp数组的含义  2)递推公式  3)dp数组的初始化  4)遍历顺序的讨论  5、代码  Ⅱ、一维数组解01背包  1)一维数组|滚动数组  2)一维数组的含义及递

    2024年02月02日
    浏览(45)
  • 背包问题(贪心)& 二维01背包问题 Java

    题目描述 有n件物品和一个最大承重为w 的背包。第i件物品的重量是weight[i],每件只能用一次,求装入背包的最多物品数量。 题目分析 因为我们 只要求装入物品的数量 ,所以 装重的显然没有装轻的划算 。 因此将 数组weight[i]按从小到大排序 , 依次选择每个物品 ,直到装不

    2024年01月17日
    浏览(40)
  • 01背包问题——以小明的背包1 为例

    本文旨在加强01背包问题的记忆与理解,步骤会细化 小明有一个容量为 VV的背包。 这天他去商场购物,商场一共有 N 件物品,第 i 件物品的体积为 w ,价值为 v 。 小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少,请你帮他算算。 输入描述 输入第

    2023年04月14日
    浏览(32)
  • leetcode刷题之背包问题(01背包)

    01 背包 概念:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是 w e i g h t [ i ] weight[i] w e i g h t [ i ] ,得到的价值是 v a l u e [ i ] value[i] v a l u e [ i ] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。 方法1:暴力回溯法 方法2:动态规划 三个

    2024年02月02日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包