PROSAGA码农传奇-运筹学-找到能带来最大利润的组合

<div class =“post-text”itemprop =“text”>
  
    这是一个
     <code>
 O(2n + sort)
 </code>
     在大多数情况下应该产生良好结果的算法
  
  <OL>
    <LI>
      计算每个项目的产量（
       <code>
 item.yield = item.profit / item.cost
 </code>
      ）
    </LI>
    <LI>
      按产量排序项目（最高产量率）
    </LI>
    <LI>
      迭代分类项目
       <code>
 remaining_budget > 0
 </code>
    </LI>
    <LI>
      采购
       <code>
 number_of_items = floor(remaining_budget / item.cost)
 </code>
       的
       <code>
 item.id
 </code>
      ， 减去
       <code>
 number_of_items * item.cost
 </code>
       从
       <code>
 remaining_cost
 </code>
    </LI>
  </醇>
  
    如果您是离散操作，它不会总是捕获所有边缘情况，例如，说你有
     <code>
 budget = 100
 </code>
    和一个项目
     <code>
 A
 </code>
     同
     <code>
 cost = 51, yield = 1.5
 </code>
     和另一个项目
     <code>
 B
 </code>
     同
     <code>
 cost = 50, yield = 1.4
 </code>
    ，
  
  <UL>
    <LI>
       <code>
 100 - 51 = 49
 </code>
       +
       <code>
 51 * 1.5 = 76.5
 </code>
       =
       <code>
 125
 </code>
      ，
       
      
一
       <code>
 A
 </code>
       结果是
       <code>
 25.5
 </code>
       利润
    </LI>
    <LI>
       <code>
 100 - 2 * 50 = 0
 </code>
       +
       <code>
 2 *
 </code>
       <code>
 50 * 1.4 = 70
 </code>
       =
       <code>
 140
 </code>
      ，
       
      
二
       <code>
 B
 </code>
      结果
       <code>
 40
 </code>
       利润，
       
      
即，由于更有效地使用整个预算，购买两个更差的个人更好
    </LI>
  </UL>
  
    但是，如果您持续运营，它将开始提高绩效，因为预算不再是一个限制因素
  
  <HR />
  
    优化可能包括
  
  <UL>
    <LI>
      在排序时计算产量，在整个数据结构上迭代一次
    </LI>
    <LI>
      删除排序步骤，而是在迭代时“丢弃”更糟糕的选择，这最终可能需要更长时间才能完成
    </LI>
    <LI>
      结束迭代时
       <code>
 remaining_budget < minumum_unit_cost
 </code>
      ，例如如果有很多高/中等成本但没有/很少有低成本，你可以提前停止迭代
    </LI>
  </UL>
</DIV>