APCS程式檢測 -實作題1061028 第4題 物品堆疊

APCS程式檢測 -實作題1061028 第4題 物品堆疊

本題會使用到 C++ 的 STL vector，如果不熟悉的話可以來這裡看看
https://husking-studio.com/cpp-stl-vector/

這題的解題方式是依序插入
每次插入的時候都計算一次最佳排序
再決定插入的位置

題目說明1

題目說明2

計算取用能量

//計算取用能量
int GetEnergy(vector<int> vecData, int* w, int* f)
{
	int nCargoNum1 = 0;
	int nCargoNum2 = 0;

	int nAllWeight1 = 0;
	int nAllWeight2 = 0;
	int nAllWeight3 = 0;

	for (int i = 0; i < (int)vecData.size(); i++)
	{
		nCargoNum1 = vecData[i];
		nAllWeight1 = 0;
		for (int j = 0; j < i; j++)	//疊在上面的重量加總
		{
			nCargoNum2 = vecData[j];
			nAllWeight1 += w[nCargoNum2];
		}
		nAllWeight2 = nAllWeight1 * f[nCargoNum1];	//重量加總 * 取用次數
		nAllWeight3 += nAllWeight2;		//再全部加總
	}

	return nAllWeight3;
}

尋找能量最小的插入位置

//尋找能量最小的插入位置
int GetInsertIndex(vector<int> vecData, int nDataNum, int* w, int* f)
{
	vector<int> vecDataTemp;
	vector<int>::iterator it;

	int nEnergy = 0;
	int nEnergyMin = 0;
	int nInsertIndex = 0;

	for (int i = 0; i <= (int)vecData.size(); i++)	//每一格都插入看看
	{
		vecDataTemp = vecData;

		if (i == (int)vecData.size())
		{
			vecDataTemp.push_back(nDataNum);
		}
		else
		{
			it = GetVectorItByIndex(&vecDataTemp, i);
			vecDataTemp.insert(it, nDataNum);
		}

		nEnergy = GetEnergy(vecDataTemp, w ,f);	//算出每一次需要的能量

		//找出最小的能量，並記錄插入的是哪一格
		if (i == 0)
		{
			nEnergyMin = nEnergy;
			nInsertIndex = 0;
		}
		else
		{
			if (nEnergy < nEnergyMin)
			{
				nEnergyMin = nEnergy;
				nInsertIndex = i;
			}
		}
	}

	return nInsertIndex;
}

完整程式碼

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

int GetEnergy(vector<int> vecData, int* w, int* f);//計算取用能量
int GetInsertIndex(vector<int> vecData, int nDataNum, int* w, int* f);//尋找能量最小的插入位置
vector<int>::iterator GetVectorItByIndex(vector<int>* pVector, int nIndex);

int main()
{
	//輸入物品數量
	string strInput;
	getline(cin, strInput);
	int nCargoNum = stoi(strInput);
	int nCargoArrayNum = nCargoNum + 1;

	//宣告陣列
	int* w = new int[nCargoArrayNum];	//重量
	int* f = new int[nCargoArrayNum];	//取用次數

	for (int i = 0; i < nCargoArrayNum; i++)
	{
		w[i] = 0;
		f[i] = 0;
	}

	//輸入物品重量
	string strInput2;
	getline(cin, strInput2);
	stringstream delim2(strInput2);
	string pch2;
	for (int i = 0; i < nCargoNum; i++)
	{
		getline(delim2, pch2, ' ');
		w[i + 1] = stoi(pch2);
	}

	//輸入物品取用次數
	string strInput3;
	getline(cin, strInput3);
	stringstream delim3(strInput3);
	string pch3;
	for (int i = 0; i < nCargoNum; i++)
	{
		getline(delim3, pch3, ' ');
		f[i + 1] = stoi(pch3);
	}

	//排列順序 vector
	vector<int> vecCargo;
	vecCargo.push_back(1);

	int nInsertIndex = -1;
	vector<int>::iterator insertIt;
	for (int i = 2; i <= nCargoNum; i++)	//依序插入
	{
		nInsertIndex = GetInsertIndex(vecCargo, i, w, f);	//尋找能量最小的插入位置

		if (nInsertIndex == (int)vecCargo.size())
		{
			vecCargo.push_back(i);
		}
		else
		{
			insertIt = GetVectorItByIndex(&vecCargo, nInsertIndex);
			vecCargo.insert(insertIt, i);
		}
	}

	cout << GetEnergy(vecCargo, w, f) << endl;

	delete[] w;
	delete[] f;

	system("pause");
	return 0;
}
//尋找能量最小的插入位置
int GetInsertIndex(vector<int> vecData, int nDataNum, int* w, int* f)
{
	vector<int> vecDataTemp;
	vector<int>::iterator it;

	int nEnergy = 0;
	int nEnergyMin = 0;
	int nInsertIndex = 0;

	for (int i = 0; i <= (int)vecData.size(); i++)	//每一格都插入看看
	{
		vecDataTemp = vecData;

		if (i == (int)vecData.size())
		{
			vecDataTemp.push_back(nDataNum);
		}
		else
		{
			it = GetVectorItByIndex(&vecDataTemp, i);
			vecDataTemp.insert(it, nDataNum);
		}

		nEnergy = GetEnergy(vecDataTemp, w ,f);	//算出每一次需要的能量

		//找出最小的能量，並記錄插入的是哪一格
		if (i == 0)
		{
			nEnergyMin = nEnergy;
			nInsertIndex = 0;
		}
		else
		{
			if (nEnergy < nEnergyMin)
			{
				nEnergyMin = nEnergy;
				nInsertIndex = i;
			}
		}
	}

	return nInsertIndex;
}
//計算取用能量
int GetEnergy(vector<int> vecData, int* w, int* f)
{
	int nCargoNum1 = 0;
	int nCargoNum2 = 0;

	int nAllWeight1 = 0;
	int nAllWeight2 = 0;
	int nAllWeight3 = 0;

	for (int i = 0; i < (int)vecData.size(); i++)
	{
		nCargoNum1 = vecData[i];
		nAllWeight1 = 0;
		for (int j = 0; j < i; j++)	//疊在上面的重量加總
		{
			nCargoNum2 = vecData[j];
			nAllWeight1 += w[nCargoNum2];
		}
		nAllWeight2 = nAllWeight1 * f[nCargoNum1];	//重量加總 * 取用次數
		nAllWeight3 += nAllWeight2;		//再全部加總
	}

	return nAllWeight3;
}
vector<int>::iterator GetVectorItByIndex(vector<int>* pVector, int nIndex)
{
	if (nIndex < 0 || nIndex >= (int)pVector->size())
		return pVector->end();

	vector<int>::iterator it;
	it = pVector->begin();
	for (int i = 0; i < nIndex; i++)
		it++;

	return it;
}

進階測試