Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.7 kB
6
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];
        if(weight[i] > capacity)
        {
            weight[i] = 0;
            if(weight[i] == 0)
            {
                value[i] = 0;
            }
        }
        weightSum += weight[i];
    }
    for(int i = 0; i < itemNum; i++)
    {
        cin >> value[i];
    }

    if(weightSum > capacity)
    {
        throwTrash(itemNum, weightSum, weight, value, capacity, isFirst, valueSum);
    }
    else
    {
        cout<< ";" << valueSum[0];
        return 0;
    }


    cout<< ";" << valueSum[0];
    return 0;
}

void throwTrash(int itemNum, int weightSum, int weight[], int value[], int capacity, int isFirst, int valueSum[] )
{
    int lowestValue = 101;
    int findLowest = 101;
    int record = 0;

    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])
        {
            record = i + 1;
            break;
        }
    }
    if(record != 0)
    {
        weightSum -= weight[record - 1];
        value[record - 1] = 0;
        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);
}