# Untitled

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;
}```