Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
3.4 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;
        }
        if(weight[i] > capacity)
        {
            weight[i] = 0;
        }
    }
    int k = 0;
    for(int i = 0; i < itemNum; i++)
    {
        k += value[i];
        weightSum += weight[i];
    }
    if(k == -itemNum)
    {
        cout << ";" << valueSum[0];
        return 0;
    }
    else
    {
        for(int i = 0; i < itemNum; i++)
        {
            if(value[i] == -1)
            {
                value[i] = 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 record1 = 0;
    int record2 = 0;
    int lowestValue = 10000;
    int findLowest = 10000;

    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];
                record1 = i;
            }
        }

    }
    for(int i = 0; i < itemNum; i++)
    {
        if(lowestValue == value[record1])
        {
            value[record1] = 0;
            weightSum -= weight[record1];
        for(int j = 0; j < itemNum; j++)
        {
            valueSum[0] += value[j];
        }
        for(int j = 0; j < itemNum; j++)
        {

            if(value[j] != 0)
            {
                if(isFirst == true)
            {
                isFirst = false;
            }
            else
            {
                cout << ",";
            }
                cout << j + 1;
            }
        }
        return;

        }
    }
    for(int i = 0; i < itemNum; i++)
    {
        if(findLowest > value[i] && value[i] != 0)
        {
            findLowest = value[i];
            record2 = i;
        }
    }

        if(findLowest == value[record2])
        {
            value[record2] = 0;
            weightSum -= weight[record2];
        }


    throwTrash(itemNum, weightSum, weight, value, capacity, isFirst, valueSum);
}