Untitled

#include<iostream>
#include<vector>

using namespace std;

//struct of item
struct item {
	int value = 0;
	int weight = 0;
	int idx;

	//constructor
	item(int val, int wei, int id) :value(val), weight(wei), idx(id)
	{
	}
};

void inputValues(int& itemCnt, int& capacity, vector<item>& items);
bool removeToCapacity(int capacity, int& totalValue, int& currentWeight, vector<item>& items);
void removeSmallestValue(int& totalValue, int& currentWeight, vector<item> &items);


int main()
{
	vector<item> items;
	int itemCnt = 0;  //物品數量變數 
	int capacity = 0;  //容量限制變數 
	int currentWeight = 0;
	int TotalValue = 0;

	//input values
	inputValues(itemCnt, capacity, items);

	//compute currentWeight and value
	for (auto& i : items)
	{
		TotalValue += i.value;
		currentWeight += i.weight;
	}

	while (true)
	{
		//如果已經小於capacity或消除一個就可以，跳出迴圈
		if (currentWeight < capacity || removeToCapacity(capacity, TotalValue, currentWeight, items))
		{
			break;
		}

		//不然就刪掉最小值
		removeSmallestValue(TotalValue, currentWeight, items);

		//全刪完也跳出
		if (items.size() == 0)
		{
			break;
		}
	}

	//輸出
	for (int i = 0; i < items.size(); i++)
	{
		if (i != items.size() - 1)
		{
			cout << items[i].idx << ',';
		}
		else
		{
			cout << items[i].idx;
		}
	}

	cout << ';' << TotalValue;

	return 0;
}

void inputValues(int& itemCnt, int& capacity, vector<item>& items)
{
	//輸入物品數量及容量限制 
	cin >> itemCnt >> capacity;

	//輸入重量
	for (int i = 0; i < itemCnt; i++)
	{
		items.push_back(item(0, 0, i + 1));
		cin >> items[i].weight;
	}

	//輸入各物品價值 
	for (int i = 0; i < itemCnt; i++)
		cin >> items[i].value;
}

bool removeToCapacity(int capacity, int& totalValue, int& currentWeight, vector<item>& items)
{
	int idx = -1;
	int minVal = INT_MAX;

	//找到可移除最低價值,index物件
	for (int i = items.size() - 1; i >= 0; i--)
	{
		if (currentWeight - items[i].weight <= capacity)
		{
			if (items[i].value <= minVal)
			{
				idx = i;
				minVal = items[i].value;
			}
			
		}
	}

	//return false 如果找不到
	if (idx == -1)
	{
		return false;
	}
	else
	{
		//找得到就刪掉他
		totalValue -= items[idx].value;
		items.erase(items.begin() + idx);
		return true;
	}
}

void removeSmallestValue(int& totalValue, int& currentWeight, vector<item> &items)
{
	int idx = -1;
	int minVal = INT_MAX;

	//find idx of item with smallest value or idx
	for (int i = items.size() - 1; i >= 0; i--)
	{
		if (items[i].value <= minVal)
		{
			idx = i;
			minVal = items[i].value;
		}

	}

	//刪掉最小價值物件
	currentWeight -= items[idx].weight;
	totalValue -= items[idx].value;
	items.erase(items.begin() + idx);

	return;
}