我们首先想到的自然是在初始条件W下,我们有哪些项目可以选择?我们将所有项目按照captital排序,所有小于W的都可以作为候选。自然,我们肯定会选择其中利润最大的。
我们在收取了第一个项目的利润之后,手头的资本W是变大了。这意味着我们有了更多的选择余地。于是我们可以顺着已经按照capital排序的项目来看,将小于新W的都收入候选。同样,我们会选择其中利润最大的。于是我们发现,按照利润排序的大顶堆优先队列是最理想的数据结构。
每个回合,从PQ里面取利润最大的项目,更新W(使之变大);之后再把capital小于当前W的项目入列。以此类推可以得到所需要的K个项目。
需要注意的细节是:如果PQ为空,说明当前的W太小,无法启动任何项目,就需要break。