Untitled
unknown
plain_text
2 years ago
2.5 kB
4
Indexable
#include<iostream> using namespace std; const int MAX_ITEM_NUM = 100; int main() { bool isFirst = true; int itemNum, capacity = 0; int weight[MAX_ITEM_NUM] = {0}; int value[MAX_ITEM_NUM] = {0}; int weightSum = 0; int valueSum = 0; int item[MAX_ITEM_NUM] = {0}; cin >> itemNum >> capacity; for(int i = 0; i < itemNum; i++) { item[i] = 1; } for(int i = 0; i < itemNum; i++) { cin >> weight[i]; if(weight[i] > capacity) { item[i] = 0; } if(item[i] != 0) { weightSum += weight[i]; } } for(int i = 0; i < itemNum; i++) { cin >> value[i]; } if(weightSum == 0) { cout << ";" << 0; return 0; } if(weightSum <= capacity) { for(int i = 0; i < itemNum; i++) { if(item[i] == 1) { if(isFirst == true) { isFirst = false; } else { cout << ","; } cout << i + 1; valueSum += value[i]; } } cout << ";" << valueSum; return 0; } while(true) { int lowestValue = 1000; int target1 = -1; for(int i = 0; i < itemNum; i++) { if(item i == 1) { if(weightSum - weight[i] < capacity) { if(lowestValue > value[i]) { lowestValue = value[i]; target1 = i; } } } } if(target1 != -1) { item[target1] = 0; for(int i = 0; i < itemNum; i++) { if(item[i] == 1) { if(isFirst == true) { isFirst = false; } else { cout << ","; } cout << i + 1; valueSum += value[i]; } } cout << ";" << valueSum; return 0; } } }
Editor is loading...