动态规划背包问题(例题)

动态规划背包问题(例题)发生的方式

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

动态规划题目背包问题(例题分析)

物品编号 1 2 3 4
物品体积 2 3 4 5
物品价值 3 4 5 6
求容积为8的背包能装的最大价值为多少?

解题思路

动态规划解题步骤
1)确定状态
注意: 动态规划一般要开数组,首先要明确数组的每个元素所代表的意义。
确定状态需要两个意识:(1)最后一步(2)子问题。
2)转移方程的确定
3)初始化条件和边界情况
注意:初始状态大部分都是为零,用转移方程算不出来的才需要手动定义状态。
4)计算顺序
注意:一般的计算顺序是从小到大,从上到下从左到右(二维)。

本题的状态转移方程很容易就可以得出来是f[i][j]=max(f[i-1][j], f[i-1][j-vol[i]]+val[i])
这里有两个方面需要考虑,第一个是你准备将第i件物品放入,第二是你不准备放入。所以你首先需要比较体积大小,然后比较物品价值。f[i-1][j]是你没有放入物品时的情况,f[i-1][j-vol[i]]+val[i]是你要放入物品时,计算当前物品和剩余空间价值的和。然后求他们的最大值max。

本题还提供了back(),是求解到底去了哪几件物品,是背包问题的回溯。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
using namespace std;
int val[]={ 
   0,3,4,5,6};
int vol[]={ 
   0,2,3,4,5};
int f[5][9];
bool flag[5]={ 
   true};
//背包的容积为8
//物品编号1,2,3,4
//物品容积2,3,4,5
//物品体积3,4,5,6 

int maxvalue(){ 
   
	
	for(int i=0; i<=4; i++){ 
   
		for(int j=0; j<=8; j++){ 
   
			if(i==0 || j==0){ 
   
				f[i][j]=0; 
			}else{ 
   
				if(vol[i]<=j)
					f[i][j]=max(f[i-1][j], f[i-1][j-vol[i]]+val[i]);
				else{ 
   
					f[i][j]=f[i-1][j];
				}
			}
		}
	}
	
} 

int back(int i, int j){ 
   
	if(i==0){ 
   
		for(int i=1; i<5; i++){ 
   
			if(flag[i]) cout<<i<<" ";
		}
	}
	if(f[i][j]==f[i-1][j]){ 
   
		back(i-1,j);
	}
	else if(f[i][j]==f[i-1][j-vol[i]]+val[i]){ 
   
		flag[i]=true;
		back(i-1,j-vol[i]);
	}
}

int main(){ 
   
	maxvalue();
	for(int i=0; i<=4; i++){ 
   
		for(int j=0; j<=8; j++){ 
   
			printf("%4d",f[i][j]);
		}
		cout<<endl;
	}
	
	back(4,8);
	return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164411.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Hadoop框架:NameNode工作机制详解

    Hadoop框架:NameNode工作机制详解

    2020年11月20日
  • H5添加QQ好友的链接

    tencent://AddContact/?fromId=45&amp;fromSubId=1&amp;subcmd=all&amp;uin=你的QQ号&amp;website=www.oicqzone.com既点击有如下效果:

  • accept text/html,Accept_标题 | Headers_HTTP_参考手册_非常教程

    accept text/html,Accept_标题 | Headers_HTTP_参考手册_非常教程AcceptAccept请求的HTTP标头通告了内容类型,并表示为MIME类型,客户端是能够理解的。使用内容协商,服务器然后选择其中一个提议,使用它并通过Content-Type响应头通知客户它的选择。浏览器根据请求完成的上下文为此标头设置足够的值:在获取CSS样式表时,为请求设置的值与获取图像,视频或脚本时的值不同。HeadertypeRequestheaderForbidden…

  • Autoconf 详解[通俗易懂]

    Autoconf 详解[通俗易懂]AutoconfCreatingAutomaticConfigurationScriptsEdition2.13,forAutoconfversion2.13December1998byDavidMacKenzieandBenElliston目录介绍创建configure脚本编写`configure.in用autoscan创建`configure.in用if

  • 【转载】视频跟踪的研究

    首先,什么是视频跟踪?基于视频的运动目标跟踪技术作为计算机视觉领域的核心研究课题之一, 主要目的是模仿生理视觉系统的运动感知功能,通过对摄像头捕捉到的图像序列进行分析,计算出运动目标在每一帧图像中的二维坐标位置;然后,根据运动目标相关的特征值,将图像序列中连续帧间的同一运动目标关联起来,得到每帧图像中目标的运动参数以及相邻帧图像间运动目标的对应关系,从而得到各个运动目标完整的运动轨迹,即在

  • android studio怎么用真机调试_android studio调试

    android studio怎么用真机调试_android studio调试在使用androidstudio进行项目的调试的时候,模拟器真的有点慢,有时还很卡,大家可能还是更想使用真机进行调试,那么下面来看看androidstudio如何使用真机测试app的教程。第一大步,先对androidstudio进行设置:1、进入AndroidStudio界面,找到界面左侧工具栏的app2、鼠标点击app,在弹出的列表中选择EditConfigurations这一项3、在…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号