一起学习交流~

背包-01-动态规划01背包问题

算法 laomuji 11个月前 (11-11) 425次浏览 已收录 0个评论

一、场景模拟

假设背包容量为6,一共有4个物品,求最大可装入背包的价值,物品如下表

编号重量价格
000
1215
2320
3430
4540

如果使用贪心算法,装4号物品,然后重量剩余1,无法装其它物品,最大价值为40,显然并不是最优解

所以需要使用DP动态规划

二、贪心算法和动态规划的区别

贪心算法:取当前情况的最优解,自上到底

动态规划:通过之前的最优解,得到当前的最优解,自低到上

三、思路

物品重量若大于背包重量,肯定是不能装的

如果可以装入背包,那么该物品有或者不装两种状态

需要判断,是装当前的物品还是不装当前物品的价值高

不仅要考虑只装入当前物品的价值,还要考虑剩余的容量和物品可以装的价值

编号重量0重量1重量2重量3重量4重量5重量6
00000000
1001515151515
2001520203535
3001520303545
4001520304045

比如:

最大价值(编号1,重量1):

编号为1的物品,重量为2,小于重量1的情况,所以无法装入背包


最大价值(编号2,重量5):

编号为2的物品,重量为3,小于重量5的情况,所以可以装入背包

装入背包:

当前物品价值:20

剩余重量:5-3=2

剩余编号:2-1=1

剩余的价值=(编号1,重量2)=15

装入背包的价值=当前物品价值+剩余的价值=20+15=35

不装入背包:

剩余重量:5

剩余编号:2-1=1

不装入背包的价值=(编号1,重量5)=15

最高价值=max(装入背包价值,不装入背包价值)=35>15=35


最大价值(编号4,重量6):

编号为4的物品,重量为5,小于重量6的情况,所以可以装入背包

装入背包:

当前物品价值:40

剩余重量:6-5=1

剩余编号:4-1=3

剩余的价值=(编号3,重量1)=0

装入背包的价值=当前物品价值+剩余的价值=40+0=40

不装入背包:

剩余重量:6

剩余编号:4-1=3

不装入背包的价值=(编号3,重量6)=45

最高价值=max(装入背包价值,不装入背包价值)=40<45=45

四、代码

#include<iostream>
#include<iomanip>
#define MaxSize 10
using namespace std;

int main()
{
	//为了方便编写,把下标为0的当作编号0以及重量0
	int n = 4;//物品数量
	int weights[MaxSize] = { 0,2,3,4,5 };//重量
	int values[MaxSize] = { 0,15,20,30,40 };//价值
	int backpackCapacity = 6;//背包容量
	int result[MaxSize][MaxSize] = {0};//存放结果

	//迭代物品编号
	for (int i = 1; i <= n; i++)
	{
		//迭代物品重量
		for (int j = 1; j <= backpackCapacity; j++)
		{
			if (weights[i] > j)
			{
				//如果当前重量太小,无法把当前物品装入背包
				result[i][j] = result[i-1][j];
			}
			else
			{
				//如果当前重量可以把当前物品装入背包
				//比较装或者不装当前物品的收益
				
				//装当前物品,也就是说最大价值为:当前价值 + (物品编号-1,物品重量-当前重量) 的价值
				int inBackpackValue = values[i] + result[i - 1][j - weights[i]];
				//不装当前物品,也就是说物品编号-1,物品重量不变
				int notInBackpackValue = result[i - 1][j];

				//装当前物品的价值和不装当前物品的价值进行比较,哪个高,就是最大价值
				result[i][j] = max(inBackpackValue, notInBackpackValue);
			}
		}
	}

	cout << "最大价值为:"<< result[n][backpackCapacity] << endl;

	//显示表
	cout << setw(7) << "编 号";
	for (int j = 0; j <= backpackCapacity; j++)
	{
		cout << setw(6) << "重量" << j;
	}
	cout << endl;
	for (int i = 0; i <= n; i++)
	{
		cout << setw(7) << i;
		for (int j = 0; j <= backpackCapacity; j++)
		{
			cout << setw(7) << result[i][j];
		}
		cout << endl;
	}
	return 0;
}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论