【c++回顾】3.1经典算法问题-混合背包问题

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【c++回顾】3.1经典算法问题-混合背包问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4664字，纯文字阅读大概需要7分钟。

内容图文

问题描述：
给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？每种物品有ni个或无限个
问题分析：
利用我的上一篇博客多重背包填满问题的程序，只需要将无限个物品的数量设置为INT_MAX即可
代码如下：

//给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？每种物品有ni个或无限个
//利用多重背包填满问题的程序，只需要将无限个物品的数量设置为INT_MAX即可

#include "pch.h"
#include <iostream>
#include <vector>
using namespace std;
//int型取最小值
int Min_int(int a, int b)
{
	return a > b ? b : a;
}
//int型取最大值
int Max_int(int a, int b)
{
	return a > b ? a : b;
}
//打印拿取方案
void PrintVector(vector<int> take_or_not)
{
	cout << "【最佳拿取方案】" << endl;
	for (int i = 0; i < take_or_not.size(); i++)
	{
		cout << "拿取" << "第" << i << "个物品:" << take_or_not[i] << " 个" << endl;
	}
	cout << endl;
}
//给出拿取情况向量与重量列表向量，求解当前背包重量,也可以用于求解价值
int CalculateWeight(vector<int> taken_items, vector<int> weights)
{
	int weight = 0;
	for (int i = 0; i < taken_items.size(); i++)
		weight = weight + taken_items[i] * weights[i];
	return weight;
}
//判断剩余空间能否放下从i开始的某个物品，一个都放不了则返回False
bool TakeMore(vector<int> weights, vector<int> number_i, vector<int> take_or_not, int left_capacity, int i)
{
	for (; i < weights.size(); i++)
	{
		if (weights[i] <= left_capacity && take_or_not[i] < number_i[i])
			return true;
	}
	return false;
}
/*递归解决该问题*/
//给出背包（剩余）容量，物品重量列表，拿取方案列表，要拿取的物品位置i
//主函数调用时先初始化take_or_not与i为0
//该问题中，solutions用于存储所有使背包饱和的拿取方案
//不同于完全背包问题，多重背包问题中还需要增加每个物品只有n个的限制条件
void Recursion(int capacity, vector<int> weights, vector<int> number_i, vector<int>& take_or_not, int i, vector<vector<int>>& solutions)
{
	int left_capacity = capacity - CalculateWeight(take_or_not, weights);
	//如果已经到最后一个物品，则直接用最后一个物品装满背包，进行操作，并返回
	if (i == (take_or_not.size() - 1))
	{
		//最后一个物品尽可能多拿
		take_or_not[i] = Min_int(left_capacity / weights[i], number_i[i]);
		//更新left_capacity
		left_capacity = capacity - CalculateWeight(take_or_not, weights);
		if (take_or_not[i] >= 0)
		{
			//判断当前拿取方案是否饱和，如果每个物品都放不下了再进行操作
			if (!TakeMore(weights, number_i, take_or_not, left_capacity, 0))
			{
				//operation,存储当前拿取方案
				solutions.push_back(take_or_not);
			}
		}
		//返回前将最后一个物品清空
		take_or_not[i] = 0;
		return;
	}
	//定义flag，用于判断是否执行了for循环
	bool flag = false;
	//第i个物品数量从0开始递增，直到装满背包或物品用完为止，每加1就对i+1进行递归
	for (int o = 0; weights[i] <= left_capacity && o <= number_i[i]; o++)
	{
		take_or_not[i] = o;
		//更新left_capacity
		left_capacity = capacity - CalculateWeight(take_or_not, weights);
		Recursion(capacity, weights, number_i, take_or_not, i + 1, solutions);
		flag = true;
	}
	//如果当前i不是最后一个物品,且未执行for循环，则继续递归
	if (i != take_or_not.size() - 1 && !flag)
		Recursion(capacity, weights, number_i, take_or_not, i + 1, solutions);
	//当前物品遍历结束后，该物品数量清零并返回
	take_or_not[i] = 0;
	return;
}
//在solution中查找并输出背包价值最大值及最佳拿取方案
void Backpack(vector<vector<int>> solutions, vector<int> values)
{
	//定义最大价值，初始化为0
	int max_value = 0;
	//第一次遍历，求得最大值，并输出
	for (auto solution : solutions)
	{
		int current_value = CalculateWeight(solution, values);
		max_value = max_value > current_value ? max_value : current_value;
	}
	cout << "【背包最大价值】" << endl << max_value << endl;
	//第二次遍历，求得最佳拿取方案，并输出
	for (auto solution : solutions)
	{
		int current_value = CalculateWeight(solution, values);
		if (current_value == max_value)
			PrintVector(solution);
	}
}
int main()
{
	//初始化
	int capacity;
	vector<int> weights;
	vector<int> values;
	vector<int> number_i;
	int number;
	cout << "输入背包容量及物品件数：" << endl;
	cin >> capacity >> number;
	cout << "输入这" << number << "个物品的重量" << endl;
	for (int i = 0; i < number; i++)
	{
		int weight;
		cin >> weight;
		weights.push_back(weight);
	}
	cout << "输入这" << number << "个物品的价值" << endl;
	for (int i = 0; i < number; i++)
	{
		int value;
		cin >> value;
		values.push_back(value);
	}
	cout << "输入这" << number << "个物品的个数(输入-1则为无限个)" << endl;
	for (int i = 0; i < number; i++)
	{
		int n;
		cin >> n;
		if (n == -1)
			n = INT_MAX;
		number_i.push_back(n);
	}
	//定义拿取方案，用于递归
	vector<int> take_or_not(number, 0);
	//定义递归操作符
	int i = 0;
	//定义solutions，用于存储所有使背包饱和的拿取方案
	vector<vector<int>> solutions;
	//递归获取所有solution
	Recursion(capacity, weights, number_i, take_or_not, i, solutions);
	//在solution中查找并输出背包价值最大值及最佳拿取方案
	Backpack(solutions, values);

	return 0;
}

内容总结

以上是互联网集市为您收集整理的【c++回顾】3.1经典算法问题-混合背包问题全部内容，希望文章能够帮你解决【c++回顾】3.1经典算法问题-混合背包问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---