Pythonで分数ナップサック問題を実装するプログラム

同じ長さの重みと値、および別の値容量の2つのリストがあるとします。 weights[i]とvalues[i]は、i番目の要素の重みと値を表します。したがって、最大で容量の重みを取得でき、比例した値でアイテムの重みの一部を取得できる場合は、取得できる値の最大量を見つける必要があります（最も近い整数に切り捨てられます）

したがって、入力が重み=[6、7、3]値=[110、120、2]容量=10のような場合、出力は178になります。

これを解決するには、次の手順に従います-

• res：=0

  • 重みと値を使用してペアPのリストを作成し、重みごとの値に基づいて並べ替えます

  • Pのペアごとに、実行します

    • cif容量が0の場合、

      • ループから出てきます

    • pair [0]>容量の場合、

      • res：=res +（pair [1] /（pair [0] / capacity）

        の商

      • 容量：=0

    • それ以外の場合、pair [0] <=容量の場合、

      • res：=res+ペア[1]

      • 容量：=容量-ペア[0]

  • resのリターンフロア値

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, weights, values, capacity):
      res = 0
      for pair in sorted(zip(weights, values), key=lambda x: - x[1]/x[0]):
         if not bool(capacity):
            break
         if pair[0] > capacity:
            res += int(pair[1] / (pair[0] / capacity))
            capacity = 0
         elif pair[0] <= capacity:
            res += pair[1]
            capacity -= pair[0]
      return int(res)

ob = Solution()
weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))

入力

[6, 7, 3],[110, 120, 2],10

出力

230