algorithm - 竞赛挑战 : "Maximize number of races one can take part in"

Question

在练习 hackerearth 的问题时，我遇到了以下问题(不是来自 active contest )并且在多次尝试后都没有成功。

Chandler is participating in a race competition involving N track races. He wants to run his old car on these tracks having F amount of initial fuel. At the end of each race, Chandler spends si fuel and gains some money using which he adds ei amount of fuel to his car.

Also for participating in race i at any stage, Chandler should have more than si amount of fuel. Also he can participate in race i once. Help Chandler in maximizing the number of races he can take part in if he has a choice to participate in the given races in any order.

我该如何解决这个问题。我的方法是按 (ei-si) 排序，但我无法合并当前燃料大于比赛所需的条件。

编辑 我尝试使用以下算法解决但它失败了，我也想不出任何使算法失败的输入。请帮我找出问题所在，或者在我的算法失败时提供一些意见。

Sort (ei-si) in non-increasing order;
start iterating through sorted (ei-si) and find first element such that fuel>=si
   update fuel=fuel+(ei-si);
   update count;
   erase that element from list, and start searching again;

if fuel was not updated than we can't take part in any races so stop searching 
and output count.

编辑 这是我要求的代码。

#include<iostream>
#include<vector>
#include<algorithm>
#include<list>

using namespace std;
struct race{
    int ei;
    int si;
    int earn;


};

bool compareByEarn(const race &a, const race &b)
{
    return a.earn <= b.earn;
}

int main(){

    int t;
    cin>>t;
    while(t--){
        vector<struct race> fuel;
        int f,n;
        cin>>f>>n;
        int si,ei;
        while(n--){
            cin>>si>>ei;
            fuel.push_back({ei,si,ei-si});

        }
        sort(fuel.begin(),fuel.end(),compareByEarn);
        list<struct race> temp;
        std::copy( fuel.rbegin(), fuel.rend(), std::back_inserter(temp ) );


        int count=0;
        while(1){


            int flag=0;
            for (list<struct race>::iterator ci = temp.begin(); ci != temp.end(); ++ci){
                if(ci->si<=f){
                    f+=ci->earn;
                    ci=temp.erase(ci);
                    ++count;
                    flag=1;
                    break;

                }
            }

            if(!flag){
                break;
            }
        }

        cout<<count<<endl;

    }


}

编辑 正如下面的回答所述，上述贪婪方法并不总是有效。所以现在任何替代方法都会有用

Answer 1

这是我的解决方案，已被法官接受:

1. 淘汰那些有利润的种族 (ei>si)
2. 按ei排序(降序)
3. 使用动态规划算法解决问题。 (类似于0-1背包的伪多项式解。)

很明显，您淘汰有利可图的比赛的顺序并不重要。 (只要您处理它们，直到无法进入更多有利可图的比赛。)

剩下的，我先证明，如果存在解，你可以按照ei递减的顺序进行同样的一组比赛，解仍然是可行的。想象一下，我们有一个解决方案，其中选择了 k 场比赛，假设这 k 场比赛的开始和结束燃料值为 s1,...,sk 和 e1,...,ek。让 i 成为第一个索引，其中 ei < ej(其中 j=i+1)。我们将证明我们可以在不违反任何约束的情况下交换 i 和 i+1。

很明显，交换 i 和 i+1 不会破坏 i 之前或 i+1 之后的任何约束，所以我们只需要证明如果我们将其顺序与比赛 i+1 交换，我们仍然可以执行比赛 i ( j).按照正常的顺序，如果我们在第 i 场比赛开始之前的燃油水平是 f，那么在第 i 场比赛之后它将是 f-si+ei，这至少是 sj。也就是说，我们有:f-si+ei>=sj，即f-sj+ei>=si。然而，我们知道 ei < ej 所以 f-sj+ej >= f-sj+ei >= si，因此在第 i 场比赛之前的第 j 场比赛仍然会为第 i 场比赛留下至少 si 燃料。

从那里，我们实现了一个动态规划算法，其中 d[i][j] 是我们可以参加的最大比赛数量，如果我们只能使用比赛 i..n 并且我们从 j 单位燃料开始。

这是我的代码:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 110;
const int maxf = 110*1000;

int d[maxn][maxf];

struct Race {
    int s, e;
    bool used;
    inline bool operator < (const Race &o) const {
        return e > o.e;
    }
} race[maxn];

int main() {
    int t;
    for (cin >> t; t--;) {
        memset(d, 0, sizeof d);

        int f, n;
        cin >> f >> n;

        for (int i = 0; i < n; i++) {
            cin >> race[i].s >> race[i].e;
            race[i].used = false;
        }

        sort(race, race + n);

        int count = 0;

        bool found;
        do {
            found = 0;
            for (int i = 0; i < n; i++)
            if (!race[i].used && race[i].e >= race[i].s && race[i].s >= f) {
                race[i].used = true;
                count++;
                f += race[i].s - race[i].e;
                found = true;
            }
        } while (found);


        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < maxf; j++) {
                d[i][j] = d[i + 1][j];
                if (!race[i].used && j >= race[i].s) {
                    int f2 = j - race[i].s + race[i].e;
                    if (f2 < maxf)
                        d[i][j] = max(d[i][j], 1 + d[i + 1][f2]);
                }
            }
        }

        cout << d[0][f] + count << endl;
    }

    return 0;
}