中興--維克多博士問題（背包問題更新版）

題目描述：

維克多博士創造了一個裂變反應堆，可取用處于液體狀态的放射性物質。反應堆的容量是V加侖。他有N瓶的放射性液體，每個都有一定的品質和一定的體積。當液體倒入反應堆時，也産生一些機關的能量。現在，維克多想要将能量輸出最大化。但是，有一個限制條件。他研究了原子元素的實體知識和曆史，認識到反應堆内放射性液體的總量不能超過特定的臨界品質M，否則反應就會失控，并引發劇烈的爆炸。寫一個算法，幫助他從反應堆獲得最大的能量，而不會讓他丢掉性命。

輸入：

該函數/方法的輸入包括六個參數------

reactorCap，一個整數，表示反應堆的容量(V);

numberOfRadLiquid,一個整數，表示現有小瓶的數量(N);

criticalMass，一個整數，表示反應堆的最大臨界品質(M);

volumes，一個整數清單，按順序表示N份放射性液體的體積;

masses，一個整數清單，按順序表示N份放射性液體的品質;

energies,一個整數清單，按順序表示N份放射性液體産生的能量。

輸出：

傳回一個整數，表示可給定的限制條件下從反應堆中産生的最大能量。

示例：

輸入：

reactorCap=100

numberOfRadLiquid=5

criticalMass=15

volumes=[50,40,30,20,10]

masses=[1,2,3,9,5]

energies=[300,480,270,200,180]

輸出：

960

解釋：

通過選擇1、2、5号瓶中的液體，産生的能量=300+480+180=960。

這種液體組合産生的總體積=50+40+10=100，不大于reactorCap,造成反應堆中的總品質=1+2+5=8，不大于criticalMass。

解題思路：這是一個有兩個限制條件的0-1背包問題，0-1背包問題可以參考我的另一篇博文：0-1背包問題，這裡隻需将一個限制條件的二維動态規劃表變成一個三維動态規劃表。

int maxEnergyGenerate(int reactorCap, int numberOfRadLiquid, int criticalMass, int *volumes, int *messes, int *energies)
{
	vector<vector<vector <int>>> maxValue;
	vector<vector <int>> tmpTmp;
	vector<int> tmp;
	for (int i = 0; i < numberOfRadLiquid + 1; i++)
	{
		for (int j = 0; j < reactorCap + 1; j++)
		{
			for (int k = 0; k < criticalMass + 1; k++)
			{
				tmp.push_back(0);
			}
			tmpTmp.push_back(tmp);
			tmp.clear();
		}
		maxValue.push_back(tmpTmp);
		tmpTmp.clear();
	}

	for (int i = 1; i <= numberOfRadLiquid; i++)
	{
		for (int j = 1; j <= reactorCap; j++)
		{
			for (int k = 1; k <= criticalMass; k++)
			{
				if (i == 1)
				{
					if ((volumes[i - 1] <= j) && (messes[i - 1] <= k))
					{
						maxValue[i][j][k] = energies[i - 1];
					}
					else
					{
						maxValue[i][j][k] = 0;
					}
				}
				else
				{
					int topValue = maxValue[i - 1][j][k];  // 上一個網格的值
					int thisValue = ((volumes[i - 1] <= j) && (messes[i - 1] <= k) ?       // 目前商品的價值 + 剩餘空間的價值
						((k - messes[i - 1] > 0)&&(j - volumes[i - 1] > 0) ? energies[i - 1] + maxValue[i - 1][j - volumes[i - 1]][k - messes[i - 1]] :energies[i - 1])
						: topValue);
					// 傳回 topValue和thisValue中較大的一個
					maxValue[i][j][k] = (topValue > thisValue ? topValue : thisValue);
				}
			}
		}
	}
	vector<bool> result;
	for (int i = 0; i < numberOfRadLiquid; i++)
	{
		result.push_back(false);
	}
	for (int i = numberOfRadLiquid, j = reactorCap, k = criticalMass; i > 0; i--)
	{
		if (maxValue[i][j][k] > maxValue[i - 1][j][k])
		{
			result[i - 1] = true;
			j = j - volumes[i - 1];
			k = k - messes[i - 1];
		}
	}
	int sum = 0;
	for (int i = 0; i < result.size(); i++)
	{
		if (result[i])
		{
			sum += energies[i];
		}
	}
	return sum;
}