如何找到最大利润的项目编号以及如何分配数组[100000]？？？？帮我

Question

问题——一个文件被命名为“input.txt”。在此文件中，您有 100000(N) 个项目。每一项具有固定的重量 wi 和价格 pi。您最多可以使用 2036 个权重。找出方法拿物品，这样你就可以获得最大的利润。您必须打印您选择的项目以获得最大的利润。请参阅示例输出。

示例输入：

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

示例输出：

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

我已经编写了这个程序，但这里有一个问题。这里我不能设置数组大小array[100000]。如果我这样做程序会自动终止。

此外，我必须将项目名称显示为示例输出。您会发现示例输入文件 here。

//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

我不会直接给你答案，因为这要么是作业，要么是编码挑战，你应该能够自己解决。

相反，我尝试将您的代码转换成一些可读的代码，以向您展示这如何提高您对自己代码的理解

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

我使用了您的文字实现...如果您这样阅读它，它是否按照您的要求进行操作？

如何找到最大利润的项目编号以及如何分配数组[100000]？？？？帮我

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

c++

arrays

greedy