一起学习交流~

背包-02-动态规划解决完全背包

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

一、原理

废话不多说,直接讲完全背包和01背包的区别

完全背包,每个物品有无数个
和01背包基本一样,不一样的地方是,
当前物品拿k件(k>=1),或者不拿,无论拿多少件都可以
也就是说,不需要编号-1,只需要减少重量

二、表格

编号重量价格
000
1218
2320
3430
4540
编号重量0重量1重量2重量3重量4重量5重量6
00000000
1001818363654
2001820363854
3001820363854
4001820364054

三、代码

#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,18,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]];//01背包
				int inBackpackValue = values[i] + result[i][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 评论
内联反馈
查看所有评论