一起学习交流~

背包-03-多重背包及二进制优化

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

一、多重背包实现

多重背包 每种物品的数量有限,重量为W,有N种物品,每种物品有M件,求最大价值

第一感觉,转换成零一背包,利用循环,把多重背包转化为零一背包,再对零一背包进行求解

#include<iostream>
#include<iomanip>
#define MaxSize 1000
#define backpackCapacity 300
using namespace std;
int n = 4;//物品数量
int weights[MaxSize] = { 0,2,3,4,5 };//重量
int values[MaxSize] = { 0,18,20,30,40 };//价值
int sizes[MaxSize] = { 0,22,25,41,13 };//数量
int result[MaxSize * 10][backpackCapacity + 1] = { 0 };//存放结果

int main()
{
	//初始化新数组
	int n_weights[MaxSize * 10] = { 0 };//存放新重量
	int n_values[MaxSize * 10] = { 0 };//存放新价值
	int pos = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= sizes[i]; j++)
		{
			n_weights[pos] = weights[i];
			n_values[pos] = values[i];
			pos++;
		}
	}
	pos--;

	//显示新数组的数据
	for (int i = 1; i <= pos; i++)cout << n_weights[i] << " " << n_values[i] << endl;
	
	//迭代物品编号
	for (int i = 1; i <= pos; i++)
	{
		//迭代物品重量
		for (int j = 1; j <= backpackCapacity; j++)
		{
			if (n_weights[i] > j)
			{
				result[i][j] = result[i - 1][j];
			}
			else
			{
				int inBackpackValue = n_values[i] + result[i - 1][j - n_weights[i]];//01背包
				int notInBackpackValue = result[i - 1][j];
				result[i][j] = max(inBackpackValue, notInBackpackValue);
			}
		}
	}
	cout << "最大价值为:" << result[pos][backpackCapacity] << endl;
	//显示表
	cout << setw(7) << "编 号";
	for (int j = 0; j <= backpackCapacity; j++)
	{
		cout << setw(6) << "重量" << j;
	}
	cout << endl;
	for (int i = 0; i <= pos; i++)
	{
		cout << setw(7) << i;
		for (int j = 0; j <= backpackCapacity; j++)
		{
			cout << setw(7) << result[i][j];
		}
		cout << endl;
	}
	return 0;
}

虽然这样也能得到正确的结果,但是若物品的数量很大,就会导致速度很慢,占用内存很高

那么有没有办法对这些重复的数据进行优化呢?

有,那就是二进制优化,将多组重复的数据转化为2的N次方进行优化

二、二进制优化

二进制优化 就是把数字变成2的N次方

比如有个数字66,进行二进制优化,拆分为2的N次方

1 2 4 8 16 32 3

拆分成了7个数据,那么这7个数字有什么用呢?

66以内的(包括66) 任意数字,都可以由这7个数字中的几个组成

将66个数据变成了7个数据,极大减少了数据量

所有的整数,都可以使用二进制优化的方式

即使数字为百万,千万级别,也不会拆分超过百个数据

针对多重背包出现重复数据的问题,可以通过二进制优化,解决效率问题

#include<iostream>
#include<iomanip>
#define MaxSize 10000
#define backpackCapacity 30000
using namespace std;
int n = 4;//物品数量
int weights[MaxSize] = { 0,2,3,4,5 };//重量
int values[MaxSize] = { 0,18,20,30,40 };//价值
int sizes[MaxSize] = { 0,3228,2345,4121,7513 };//数量
int result[MaxSize][backpackCapacity + 1] = { 0 };//存放结果

int main()
{
	//初始化新数组
	int n_weights[MaxSize * 10] = { 0 };//存放新重量
	int n_values[MaxSize * 10] = { 0 };//存放新价值
	int pos = 1;
	for (int i = 1; i <= n; i++)
	{
		int j = sizes[i];
		int k = 1;
		while (j > k)
		{
			n_weights[pos] = weights[i] * k;
			n_values[pos] = values[i] * k;
			pos++;
			j -= k;
			k *= 2;
		}
		n_weights[pos] = weights[i] * j;
		n_values[pos] = values[i] * j;
		pos++;
	}
	pos--;

	//显示新数组的数据
	for (int i = 1; i <= pos; i++)cout << n_weights[i] << " " << n_values[i] << endl;

	//迭代物品编号
	for (int i = 1; i <= pos; i++)
	{
		//迭代物品重量
		for (int j = 1; j <= backpackCapacity; j++)
		{
			if (n_weights[i] > j)
			{
				result[i][j] = result[i - 1][j];
			}
			else
			{
				int inBackpackValue = n_values[i] + result[i - 1][j - n_weights[i]];//01背包
				int notInBackpackValue = result[i - 1][j];
				result[i][j] = max(inBackpackValue, notInBackpackValue);
			}
		}
	}
	cout << "最大价值为:" << result[pos][backpackCapacity] << endl;
	//显示表
	//cout << setw(7) << "编 号";
	//for (int j = 0; j <= backpackCapacity; j++)
	//{
	//	cout << setw(6) << "重量" << j;
	//}
	//cout << endl;
	//for (int i = 0; i <= pos; 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 评论
内联反馈
查看所有评论