四种方法解决01背包问题

这篇具有很好参考价值的文章主要介绍了四种方法解决01背包问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

01背包问题

四种方法解决01背包问题

01背包问题可以用dp或者dfs的方法来做

dfs的好处在于:它可以找出所有的选择方案,如果题目需要找方案的个数或者输出所有方案,就只能够选择dfs,而如果是用来输出最值,那么还是dp好点

dp的好处在于:dp是用来找出最优的方案,dp在每个1~V的体积总能找出当前体积下的最优方案(贪心),那么到最后他显然是输出的最优的方案,而如果要找出方案的个数,dp就显得无能为力了

 1.无优化版dp

 四种方法解决01背包问题

原问题:从前N个物品中选择,且体积不超过V的最大价值

子问题:从前i个物品中选择,且体积不超过j的最大价值

状态定义:dp[i][j]  

集合:所有从前i个物品中选择,且提及不超过j的所有方案

属性:max

状态计算/集合划分:

根据最后一个不同点,可以分为不重不漏的两个子集

  • 选择了第i个物品            dp[i-1][j-v[i]]+w[i]
  • 没有选择第i个物品        dp[i-1][j]

由于dp数组表示当前集合的最大值,所以两个子集可以划分为dp[i-1][j-v[i]]+w[i],dp[i-1][j]

#include <iostream>
#include <algorithm>
using namespace std;
int N, V;
int v[1004],w[1004];
int res[1002][1002];
int maxn = -1;

int main()
{
	memset(res, 0, sizeof(res));
	cin >> N >> V;
	for (int i = 1;i <= N;i++)
		cin >> w[i] >> v[i];
	for(int i=1;i<=N;i++)
		for (int j = 1;j <= V;j++)
		{
			if (j < w[i])
			{
				res[i+1][j] = res[i][j];
			}
			else
			{
				res[i +1][j] = max(res[i][j], res[i][j - w[i]] + v[i]);
			}
		}
	//如果采用由当前元素是否选去计数下一个元素的挑选总价值的话(下标从1开始)
	//那么结果就要改为res[N+1][V],因为此时的集合为:dp[i+1][j]=从前i个元素挑选的总体积不超过j的集合
	//这个方法的好处是,下标可以从0开始,不用考虑边界问题(只要数组稍微略出一点)


	/*如果采用到当前元素才计数他的数组值应该是多少的话(下标从1开始)
	* 那么结果仍然是res[N][M],因为此时的集合为:dp[i][j]=从前i-1个元素挑选的总体积不超过j的集合
	* 这个方法下标不可以从0开始,否则会访问到错误的地址值
	*/
	
	
	cout << res[N+1][V];
}

 解释

 在这里我记录一下dp的二维数组

i,j 1 2 3 4 5
1 2 2 2 2 2
2 2 4 6 6 6
3 2 4 6 6 8
4 2 4 6 6 8

四种方法解决01背包问题

 表格外的红色箭头表示的是仅选择了第i个元素,而斜线表示在dp[i][j]的基础上再加上他的本身,从上到下的直线表示了不选本身,只是继承了dp[i-1][j]这个值

2.记忆化搜索

本题的dfs搜索树如下

四种方法解决01背包问题

#include <iostream>
#include <algorithm>
#include <cstring> 
using namespace std;
int N, V;
int v[1004], w[1004];
int dp[1004][1004];
/*普通搜索会tle,如果要用搜索的话,本题需要浪费一定的空间来进行记忆化搜索*/
int dfs(int i, int nowv)
{/*dfs判断当前第i个物品是否能够选择,nowv表示当前的容量*/
	if (i == N + 1)			//出界return
		return 0;
	if (dp[i][nowv] > 0)
		return dp[i][nowv];
	if (nowv < w[i])				//不能挑选
	{
		return dp[i][nowv] = dfs(i + 1, nowv);
	}
	else
	{
		return dp[i][nowv] = max(dfs(i + 1, nowv), dfs(i + 1, nowv - w[i]) + v[i]);
	}
}
int main()
{
	memset(dp, 0, sizeof(dp));
	cin >> N >> V;
	for (int i = 1;i <= N;i++)
		cin >> w[i] >> v[i];
	cout << dfs(1, V);
}

3.滚动数组法

时间复杂度没有降低,但是降低了空间复杂度

这里dp数组只用了两行来存储

#include <iostream>
#include <algorithm>
#include <cstring> 
using namespace std;
const int MAXN = 1100;
int v[MAXN], w[MAXN], dp[2][MAXN];
int main() {
    int N, V; cin >> N >> V;
    for (int i = 1; i <= N; ++i) cin >> w[i] >> v[i];
    /*我们知道dp的递推式是:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
    从这个可以看出每一项的数组值都只会来自于dp数组的上面一行,而再上面的一行可以看到并不需要使用到
    所以我们就采用了一个滚动数组的方法,运用类似循环的方法来存储dp数组
    这里 在第二重for循环里 t2表示的是当前数组,t1表示的是上一个数组
    当整个dp循环结束后,t1表达的是结果(最下面的一行dp数组)
    这个方法并不需要去管他有多少个物品,可以降低空间复杂度
    */
    int* t1 = dp[0];            //滚动数组第一行指针
    int* t2 = dp[1];            //滚动数组第二行指针
    for (int i = 1;i <= N;i++)
    {
        for (int j = 1;j <= V;j++)
        {
            if (j < w[i])
                t2[j] = t1[j];
            else
                t2[j] = max(t1[j], t1[j - w[i]] + v[i]);
        }
        swap(t1, t2);
    }
    cout << t1[V] << endl;

}

4.一维优化dp法

这个方法比滚动数组法更加极致,仅用了一行来存储dp数组,极大降低了空间复杂度

dp的一维优化,首先要保证的是,在进行集合划分/状态计算时,前面两个子集合的值已经被递推出来了并且存在

如果我们仍采用j从0~V遍历的话,其实可以看到

四种方法解决01背包问题

枚举到j时,前面dp[i][0~j-1]这些状态已经被计算了,不是子集和dp[i-1][0~j-1]

所以我们应该用j从V~0遍历

这样子,当集合计算时,能够保证dp[i][j]的两个子集合的值存在

最后一个被计算的集合是dp[n][0]==dp[0]

dp[n][v]==dp[v]

 文章来源地址https://www.toymoban.com/news/detail-413609.html

#include <iostream>
#include <algorithm>
#include <cstring> 
using namespace std;
const int MAXN = 1100;
int v[MAXN], w[MAXN], dp[MAXN];

int main()
{
	int N,V;
	cin >> N >> V;
	for (int i = 1;i <= N;i++)
		cin >> w[i] >> v[i];
	for(int i=1;i<=N;i++)
		for (int j = V;j >0;j--)
		{
			if (j < w[i])
				dp[j] = dp[j];
			else
			{
				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
	cout << dp[V];
	
}

到了这里,关于四种方法解决01背包问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 背包问题四种类型

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。 提示:以下是本篇

    2024年04月12日
    浏览(24)
  • 背包问题——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日
    浏览(42)
  • 背包问题分析代码详解【01背包+完全背包+多重背包】

    一、01背包问题 问题描述: 有 N 件物品和一个容量为 V 的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。 朴素01背包 状态f[i , j]定义:在前i个物品中选,总体积不超过j的价值最大值 状态转移 1) 选第i个物品:f[i,j] = f

    2024年02月06日
    浏览(37)
  • 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日
    浏览(49)
  • 01背包问题——以小明的背包1 为例

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

    2023年04月14日
    浏览(35)
  • 算法训练第四十二天|01背包问题 二维 、01背包问题 一维、416. 分割等和子集

    视频链接:https://www.bilibili.com/video/BV1cg411g7Y6/ 参考:https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 对于面试的话,其实掌握01背包,和完全背包,就够用了,最多可以再来一个多重背包。 而完全背包又是也是01背包稍作变化而来,即:完全

    2024年02月01日
    浏览(44)
  • 三十八、动态规划——背包问题( 01 背包 + 完全背包 + 多重背包 + 分组背包 + 优化)

    0 1 背包问题: 条件:N 个物品容量为 V 的背包,每件物品最多用 1 次,其中物品信息体积为 Vi,价值为 Wi。 目标:选出物品,使价值最大(不一定装满背包)。 特点:每件物品 最多只用 1 次 完全背包问题: 特点:每一件物品都有 无限个 多重背包问题: 特点:每个物品

    2024年02月07日
    浏览(49)
  • 算法系列--动态规划--背包问题(1)--01背包介绍

    💕\\\"趁着年轻,做一些比较cool的事情\\\"💕 作者:Lvzi 文章主要内容:算法系列–动态规划–背包问题(1)–01背包介绍 大家好,今天为大家带来的是 算法系列--动态规划--背包问题(1)--01背包介绍 背包问题是动态规划中经典的一类问题,经常在笔试面试中出现,是非常 具有区分度 的题

    2024年04月16日
    浏览(52)
  • 【洛谷】采药(01背包问题)

      将二维数组优化为一维数组 在上面的过程中,我们发现dp[i][j] = max(dp[i - 1][j], dp[i - 1][ j - times[i] ] + val[i]); 也就是第 i 行的数据只与第 i-1 行的数据有关,因此我们存储的 i-2 ,i-3 等都是无效的数据,那么我们可以将二维数组优化成一维数组,利用一维数组里原本存储的第

    2024年02月16日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包