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;
}

Use vectors not arrays `vector array(10000);` Problem solved. — john, Jan 10 '21 at 06:54
Does this answer your question? [C++ Object array stack overflow](https://stackoverflow.com/questions/52794875/c-object-array-stack-overflow) — JHBonarius, Jan 10 '21 at 06:55
And then the `sort` call would simply be `std::sort(arry.begin(), arry.begin() + n, compare);`. Also, you should use the correct headers, not the `bits/stdc++.h`. — PaulMcKenzie, Jan 10 '21 at 06:55
Also `#include` No! And `using namespace std;` No! Use the search function to find out why not. — JHBonarius, Jan 10 '21 at 06:56
Your title and text uses the term "2D array". I assume that means "Two dimensional array" but I don't see any code doing that... — Support Ukraine, Jan 10 '21 at 07:07
Mr. – JHBonarius i don't know what are you talking about. here I have to use greedy method — Sazid Hasan Milon, Jan 10 '21 at 07:18
@SazidHasanMilon `#include ` -- `#include ` -- `#include ` -- That bits header file should be removed and replaced with the actual, real, standard C++ headers. That is what JHBonarius is talking about. — PaulMcKenzie, Jan 10 '21 at 07:57
Do you even need to keep everything in memory ? Don't you just need th n most profitable items ? If a new one you read in is better than the least profitable item in memory then you bump out that lower profit item. — John3136, Jan 10 '21 at 07:58
Your code has a [stack overflow](https://stackoverflow.com). Don't put large objects on the stack. — David Schwartz, Jan 10 '21 at 08:02
thank you @PaulMcKenzie I added that header file to my code. I need the total profit amount and the item number. — Sazid Hasan Milon, Jan 10 '21 at 08:14
You accepted a no-answer. If you you gibe a more detailed explanation about the problem, then people can help you by providing information regarding a 0-1 or fractional Knapsack problem. And even show you an adequate implementation using either an DP or greedy algorithm. But for this to decide, we need more information in the question. — Armin Montigny, Jan 10 '21 at 13:39

score 0 · Accepted Answer · answered Jan 10 '21 at 08:32

0

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?

answered Jan 10 '21 at 08:32

JHBonarius

8,837
3
16
32

thank you. I my code compiler it's not running. There is an error. (http://prntscr.com/wk5reb), for(auto& item : items) this line.error: – Sazid Hasan Milon Jan 10 '21 at 08:42
@SazidHasanMilon see the message. You're running in C++98 mode. That's **23** years old!!! In the mean time we've had C++11, C++14, C++17 and now C++20. You should compile with something like `-std=c++17`. And note: this is not the solution to your problem. It's just a way to write it with better C++ style and proper variable naming. I hope that way you can see your own errors. – JHBonarius Jan 10 '21 at 08:47
oh my GOD i don't know, actually i amusing codeblocks v:16.01 – Sazid Hasan Milon Jan 10 '21 at 08:51
@SazidHasanMilon I dont know that IDE, but looking at [the manual](http://www.codeblocks.org/docs/main_codeblocks_en.html) it's probably under ’Settings’ →’Compiler and Debugger’. – JHBonarius Jan 10 '21 at 08:55
ok let me check it, i must say your code it very difficult to understand for me. I don't know much about vector funtion. – Sazid Hasan Milon Jan 10 '21 at 09:01
2

@SazidHasanMilon then maybe you should start learning C++ using a good book or other resource. Check [this](https://stackoverflow.com/a/388282). Don't just plunge into the deep by doing complex assignments. You'll teach yourself bad habits. – JHBonarius Jan 10 '21 at 09:07

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

1 Answers1