# 第三題

unknown
plain_text
7 months ago
2.5 kB
0
Indexable
Never
```#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++;
}
}
}```