Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.0 kB
3
Indexable
Never
#include<iostream>
using namespace std;
const int MAX = 100;
int Sort(int capacity, int currentWeight, int weight[], int K[], int itemCnt);

int main()
{
	int itemCnt = 0;  //物品數量變數 
	int capacity = 0;  //容量限制變數 
	int weight[MAX] = { 0 };   //各物品重量陣列 
	int value[MAX] = { 0 };  //各物品價值陣列 
	int selectedItem[MAX] = { 0 };
	int currentWeight = 0;
	int TotalValue = 0;
	int K[MAX] = { 0 };
	int selected = 0;//總共放入幾個物品


	cin >> itemCnt >> capacity;  //輸入物品數量及容量限制 
	for (int i = 0; i < itemCnt; i++)
		cin >> weight[i];  //輸入各物品重量 
	for (int i = 0; i < itemCnt; i++)
		cin >> value[i];  //輸入各物品價值 

	while (true)
	{


		int Ksize = Sort(capacity, currentWeight, weight, K, itemCnt);  //把還沒被選且選了不會超過限制的物品放入K集合 

		//找不到便跳出
		if (Ksize == 0)
		{
			break;
		}

		int maxVal = 0;
		int idx = -1;
		for (int i = Ksize - 1; i >= 0; i--)
		{
			//找出最大value,最小編號元素之index
			if (value[K[i]] >= maxVal)
			{
				maxVal = value[K[i]];
				idx = K[i];
			}
		}

		selectedItem[selected] = idx;
		TotalValue += value[idx];
		currentWeight += weight[idx];
		weight[idx] = -1;//weight標示為-1表示已放入
		selected++;
	}

	
	for (int i = 0; i < selected; i++)
	{
		if (i != selected - 1)
		{
			cout << selectedItem[i] + 1 << ',';
		}
		else
		{
			cout << selectedItem[i] + 1;
		}
	}

	cout << ';' << TotalValue;

	return 0;
}


int Sort(int capacity, int currentWeight, int weight[], int K[], int itemCnt)  //定義Sort函式功能 
{
	int j = 0;
	for (int i = 0; i < itemCnt; i++)
	{
		//檢查可否放入以及是否已放入
		if (currentWeight + weight[i] <= capacity && weight[i] != -1)
		{
			K[j] = i;//K陣列存放可放進去元素之index
			j++;//j代表K陣列有幾個元素
		}
	}

	//回傳找到幾個元素
	return j;
}