Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
3.1 kB
0
Indexable
Never
#include<iostream>
using namespace std;

const int MAX_ITEM_NUM = 100;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    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 alsoLowestValue = 1000;
        int target1 = -5;
        int target2 = -5;
        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 != -5)
        {
            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;
            break;
        }
        for(int i = 0; i < itemNum; i++)
        {
            if(item[i] == 1)
            {
                if(weightSum - weight[i] > capacity)
                {
                    if(alsoLowestValue > value[i])
                    {
                        alsoLowestValue = value[i];
                        target2 = i;
                    }
                }
            }
        }
        if(target2 != -5)
        {
            item[target2] = 0;
        }

    }
    return 0;
}