Untitled

 avatar
unknown
plain_text
2 years ago
2.5 kB
4
Indexable
#include<iostream>
using namespace std;

const int MAX_ITEM_NUM = 100;

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 = 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 target1 = -1;
        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 != -1)
        {
            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;
            return 0;
        }
        
    }
}
Editor is loading...