如何对每个任务都有起始成本和奖励的一组任务进行排序

Question

假设你一开始有T的钱，你想找实习工作，但因为你没有经验，所以你决定购买带薪实习。

你会得到一组实习机会，每个实习机会都有一个购买成本C_b，让你先进去，一旦你进入了实习岗位，你就会拿到一些钱C_p。C_b可以大于或小于C_p，也可以与C_p相同，因此净收益可以是正收益，也可以是负收益，也可以是0。

编辑:目标是完成所有的实习。

有没有一个算法来找出所有实习的顺序(在O(n^2)中)？它可以找出是否没有办法订购，例如(剩余的钱如果不足以让你获得任何剩余的实习机会)。谢谢!

我真的很困惑，甚至不知道从哪里开始。

Answer 1

重申这个问题:你如何才能找到最有效的订单来进行买入实习，从而最大化你可以进行的实习数量。

给定：

(C_p)

• C_b C_p

• You
• 一组实习机会，每个实习机会都有买入成本(C_b)和回报额，可能大于或小于负数，但有一些money不能进入负

算法

1. 按降序按net gain对实习进行排序如果money - C_b >= 0
2. then进行实习和money = money + net gain

，则循环通过此排序的实习集

1. 重复步骤2，循环遍历跳过的实习，直到您完成一个循环而不再进行另一次实习。

使用这个算法，你将首先做报酬最高的实习，这会增加你接受更多实习的能力。

编辑

我认为一个更有效的算法是，在第二步找到合适的实习机会后，从头开始循环(以防你现在能够进行跳过的较高净收益实习之一)。