Untitled
unknown
plain_text
a year ago
3.1 kB
1
Indexable
Never
#include<iostream> using namespace std; const int MAX_ITEM_NUM = 100; void throwTrash(int itemNum, int weightSum, int weight[], int value[], int capacity, int isFirst, int valueSum[]); 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[1] = {0}; cin >> itemNum >> capacity; for(int i = 0; i < itemNum; i++) { cin >> weight[i]; } for(int i = 0; i < itemNum; i++) { cin >> value[i]; } for(int i = 0; i < itemNum; i ++) { if(weight[i] > capacity) { value[i] = -1; } } int k = 0; for(int i = 0; i < itemNum; i++) { k += value[i]; weightSum += weight[i]; } if(k == -itemNum) { cout << ";" << valueSum[0]; return 0; } throwTrash(itemNum, weightSum, weight, value, capacity, isFirst, valueSum); cout << ";" << valueSum[0]; return 0; } void throwTrash(int itemNum, int weightSum, int weight[], int value[], int capacity, int isFirst, int valueSum[] ) { int lowestValue = 1000; int findLowest = 1000; if (weightSum <= capacity) { for(int i = 0; i < itemNum; i++) { valueSum[0] += value[i]; } for(int i = 0; i < itemNum; i++) { if(value[i] != 0) { if(isFirst == true) { isFirst = false; } else { cout << ","; } cout << i + 1; } } return; } for(int i = 0; i < itemNum; i++) { if(weightSum - weight[i] <= capacity) { if(lowestValue > value[i] && value[i] != 0) { lowestValue = value[i]; } } } for(int i = 0; i < itemNum; i++) { if(lowestValue == value[i]) { value[i] = 0; weightSum -= weight[i]; for(int i = 0; i < itemNum; i++) { valueSum[0] += value[i]; } for(int i = 0; i < itemNum; i++) { if(value[i] != 0) { if(isFirst == true) { isFirst = false; } else { cout << ","; } cout << i + 1; } } return; } } for(int i = 0; i < itemNum; i++) { if(findLowest > value[i]) { findLowest = value[i]; } } for(int i = 0; i < itemNum; i++) { if(findLowest == value[i]) { value[i] = 0; weightSum -= weight[i]; break; } } throwTrash(itemNum, weightSum, weight, value, capacity, isFirst, valueSum); }