第三題

 avatar
unknown
plain_text
2 years ago
2.5 kB
4
Indexable
#include<iostream>
using namespace std;
const int MAX = 100;
void 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 set = 0;
	int x[] = {0};
	int Maxvalue = 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)
	{
		Sort(capacity, currentWeight, weight, K, itemCnt);  //把還沒被選且選了不會超過限制的物品放入K集合 
		
		for(int i = 1; i <= itemCnt; i++)
		{
			if(K[i] > 0)  //若K陣列中有一個大於零,K就不是空集合 
			  set = 1;
		}
		if(set == 0)
		  break;  //若K是空集合就跳出while 迴圈 
		else if(set == 1)
		{
			for(int i = 1;i <= itemCnt; i++)
			{
				int setNum = 0;
				setNum = K[i];
				if(Maxvalue < value[setNum-1])
				{
				   Maxvalue = value[setNum-1];
				}
			}
		}
		
		for(int i = 0; i < itemCnt; i++)
		{
			if(Maxvalue == value[i])
			{
				x[i] = 1;
				Maxvalue = 0; 
				return 0;
			}
		}
		
		for(int i = 0; i < itemCnt; i++)
		{
			int m = 0;
			if(x[i] == 1)
			{
				currentWeight += weight[i];
				weight[i] = 10000;
				TotalValue += value[i];
				selectedItem[m] = i + 1;
				m++;
				x[i] = 0;
			}
		}
	}
	
    if(selectedItem[0] == 0) //若沒有符合的號碼,輸出冒號0 
	   {
	 	cout << ";0" << endl;
		return 0 ;
	   } 
	else
	   {
		for (int i = 0; i < itemCnt; i++)
		{
		 if(selectedItem[i] > 0 && selectedItem[i+1] > 0) //若i不是最後一項要選的號碼,就輸出第i項號碼 + 逗號 
		 {
		 	cout << selectedItem[i] << ",";
		 }
		 else if(selectedItem[i] > 0)  //若i是最後一項要選的號碼,就輸出第i項號碼 + 冒號 + 價值總和 
		 {
			cout << selectedItem[i] << ";" << TotalValue << endl;
			return 0;
	     } 
	    }
	   }
	
	return 0 ;
}


void Sort(int capacity, int currentWeight, int weight[],int K[], int itemCnt)  //定義Sort函式功能 
{
	int j = 1;
	for(int i = 0; i < itemCnt; i++)
	{
		if(currentWeight + weight[i] <= capacity)
		{
			K[j] = i+1;
			j++;
	    }
	}
}
Editor is loading...