反应堆问题

题目描述

维克多博士创造了一个裂变反应堆，可取用处于液体状态的放射性物质。反应堆的容量是V加仑。他有N瓶的放射性液体，每个都有一定的质量和一定的体积。当液体倒入反应堆时，也产生一些单位的能量。现在，维克多想要将能量输出最大化。但是，有一个限制条件。他研究了原子元素的物理知识和历史，认识到反应堆内放射性液体的总量不能超过特定的临界质量M，否则反应就会失控，并引发剧烈的爆炸。

写一个算法，帮助他从反应堆获得最大的能量，而不会让他丢掉性命。

输入

该函数/方法的输入包括六个参数——

reactorCap，一个整数，表示反应堆的容量(V)；

numberOfRadLiquid，一个整数，表示现有小瓶的数量(N)；

criticalMass，一个整数，表示反应堆的最大临界质量(M)；

volumes，一个整数列表，按顺序表示N份放射性液体的体积；

masses，一个整数列表，按顺序表示N份放射性液体的质量；

energies，一个整数列表，按顺序表示N份放射性液体产生的能量。

输出

返回一个整数，表示可在给定的约束条件下从反应堆中产生的最大能量。

约束条件

1=<numberOfRadLiquid<=10^4

思路：可以用01背包问题的思路进行求解。
关于01背包问题的详细解析，可参考https://blog.csdn.net/mu399/article/details/7722810。
本题的阶梯代码如下：

int find(int reactorcap, int numberofradliquid, int criticalmass,
	int volumes[], int masses[], int energies[]) {
	vector<vector<vector<int> > > fn(numberofradliquid,vector<vector<int> >(criticalmass,(vector<int>)(reactorcap)));
	for (int i = 0; i < numberofradliquid; i++) {
		for (int j = 0; j < criticalmass; j++) {
			for (int k = 0; k < reactorcap; k++) {
				if (volumes[i] <= k + 1 && masses[i] <= j + 1) {
					//cout << i << " " << j << " " << k << " " << endl;
					if (i == 0) {
						fn[i][j][k] = fn[i][j][k] + energies[i];
					}
					else {
						fn[i][j][k] = max(fn[i - 1][j][k], fn[i - 1][j - masses[i] + 1][k - volumes[i] + 1] + energies[i]);
					}
				}
				else {
					if (i == 0) {
						fn[i][j][k] = 0;
					}
					else {
						fn[i][j][k] = fn[i - 1][j][k];
					}
				}
			}
		}
	}
	return fn[numberofradliquid-1][criticalmass-1][reactorcap-1];
}

int main()
{
	int reactorCap = 100;//容量50 
	int numberOfRadLiquid = 5;//个数
	int criticalMass = 15;//临界质量

	int volumes[5] = { 50, 40, 30, 20, 10 };//体积
	int masses[5] = { 1, 2, 3, 9, 5 };//质量
	int energies[5] = { 300, 480, 270, 200, 180 };//能量


	int sum_energies = find(reactorCap, numberOfRadLiquid, criticalMass,
		volumes, masses, energies);

	cout << sum_energies << endl;
	return 0;
}

关于背包问题的参考博文

[1] 经典背包问题的探讨 https://www.cnblogs.com/cxmhy/p/4493375.html
[2] 背包问题 https://www.cnblogs.com/shoulinniao/p/9502828.html
[3] 彻底理解01背包问题 https://blog.csdn.net/chanmufeng/article/details/82955730