第三題
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...