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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
//给定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;
}