Untitled

mail@pastecode.io avatar
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);
}