寻找能带来最大利润的组合

Question

假设我有张桌子看起来像这样：

ID成本利润

1 x- 0.55 / 1.24

2- 0.23 - 3.11

3%. 0.19 %.

4/ 0.53 / 1.49

..。诸若此类。

如果我的预算有一定的价值，我怎样才能找到最大的利润？ie:以1.12的成本找到最大利润。如果从上面的表格，我应该从ID2+3+4项目，以最大化我的利润。

我试图从LP搜索一些东西，运筹学，但我真的是盲目地谷歌，我不知道我应该寻找什么关键字。请帮帮忙。

Answer 1

你需要的是0/1背包！我从你给出的例子中假设，你需要把项目作为一个整体，而不是项目的一小部分。否则，选择默认(分数)背包。

了解贪婪的解决方案&为什么它可能失败，然后用分数阶背包动态规划的方式来解决这个问题，然后是0/1背包！这就是你应该学会解决这个问题的方法。

如果你还需要什么，请告诉我。

Answer 2

下面是一种O(2n + sort)算法，在大多数情况下会产生良好的结果。

1. 计算每个项目的产量(item.yield = item.profit / item.cost)
2. 按产量对项目进行排序(最高产量优先)
3. 在remaining_budget > 0时迭代排序项
4. 购买number_of_items = floor(remaining_budget / item.cost) of item.id，从remaining_cost中减去number_of_items * item.cost

如果您操作谨慎，它并不总是能捕捉到所有的边缘情况，例如，假设您有budget = 100，有一个带有cost = 51, yield = 1.5的项目A，有另一个带有cost = 50, yield = 1.4的项目B，

• 100 - 51 = 49 + 51 * 1.5 = 76.5 = 125 一次A带来25.5利润
• 100 - 2 * 50 = 0 + 2 * 50 * 1.4 = 70 = 140 两个B的40利润， 也就是说，由于更有效地使用整个预算，购买两个单独的更坏的预算更好

但是，如果你一直在运营，随着预算不再是一个限制因素，它将开始提高性能。

优化可能包括

• 在排序时计算产量，在整个数据结构上少迭代一次。
• 删除排序步骤，并在迭代过程中“丢弃”更糟糕的选择，这可能会花费更长的时间来完成。
• 在remaining_budget < minumum_unit_cost时结束迭代，例如，如果存在大量的高/中成本，但没有/非常少的低成本，则可以提前停止迭代。

Answer 3

这里我有一个struct数组选项代码，您可以为您的3d值数组进行修改。在这里，我使用了struct函数来处理这个程序。

struct item
{
    double w,p,u;
};

您可以使用

//Fractional Knapsack
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct item
{
    double w,p,u;
};
bool compare( item a, item b)
{
    return a.u>b.u;
}
int main()
{
    int n,w;
    item 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;
}