How to find the item number of maximum profit and how to assign array[100000]???? help me

Question

Questions – A file is given as “input.txt” name. In this file, you have 100000(N) items. Every item has a fixed weight wi and price pi. You can take maximum 2036 weights. Find out the way to take items, so that you can get maximum profit. You must print items which you have selected to get maximum profit. See, the sample output.

Sample Input:

3 (N) 3 (W)
2 10
1 4
2 20

Sample Output:

Profit: 25
Item – 3: 2 = 20
Item – 1: 1 = 5

I already coded this program but here is a problem. here i can not set the array size array[100000]. if i do the the program automatically terminated.

Also, I have to show the item name as the sample output. Sample input file here you will find.

//Fractional Knapsack
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct iteam
{
    double w,p,u;
};
bool compare( iteam a, iteam b)
{
    return a.u>b.u;
}
int main()
{
    int n,w;
    iteam arry[100];
    cin>>n>>w;
    for(int i=0; i<n; i++)
    {
        cin>>arry[i].w>>arry[i].p;
        arry[i].u = arry[i].p/arry[i].w;
    }
    sort(&arry[0],&arry[n],compare);
    int p=0;
    for (int i=0; i<n; i++)
    {
        if(w>arry[i].w)
        {
            p=p+arry[i].p;
            w=w-arry[i].w;
        }
        else{
            p=p+w*arry[i].u;
            w=0;

        }
    }
    cout<<"Total Profit: "<<p<<endl;
}

Answer 1

I'm not going to give you a straight answer, as this is either an assignment or a coding challenge, and you should be able to solve it yourself.

Instead I've tried to transform your code into some readable code, to show you how this can improve your understanding of your own code

//Fractional Knapsack
struct Item
{
    double weight;
    double profit;
    double profitPerWeight;
};

bool operator> (Item const& lhs, Item const& rhs){
    return lhs.profitPerWeight > rhs.profitPerWeight;
}

#include <iostream>
std::istream& operator>> (std::istream& in, Item& item) {
    in >> item.weight >> item.profit;
    return in;
} 

#include <vector>
#include <algorithm>

int main()
{
    int nrOfItems, maximumWeight;
    std::cin >> nrOfItems >> maximumWeight;
   
    std::vector<Item> items(nrOfItems);
    for(auto& item : items)
    {
        std::cin >> item;
        item.profitPerWeight = item.profit / item.weight;
    }

    // is this sort really needed? Think about it.
    std::sort(begin(items), end(items), std::greater<>());

    int totalProfit = 0;
    for (auto const& item : items)
    {
        if(maximumWeight > item.weight)
        {
            totalProfit += item.profit;
            maximumWeight -= item.weight;
        }
        else{
            totalProfit += maximumWeight * item.profitPerWeight;
            maximumWeight = 0;
        }
    }

    std::cout << "Total Profit: " << totalProfit << '\n';
}

I used your literal implementation... If you read it like this, does it do what you want it to?