Python에서 소수 배낭 문제를 구현하는 프로그램

<시간/>

길이가 같고 값 용량이 다른 두 개의 목록, 가중치 및 값이 있다고 가정합니다. weights[i]와 values[i]는 i번째 요소의 가중치와 값을 나타냅니다. 따라서 최대 용량 가중치를 취할 수 있고 비례 값으로 항목 가중치의 일부를 취할 수 있다면 얻을 수 있는 최대 값을 찾아야 합니다(가장 가까운 정수로 내림)

따라서 입력이 weight =[6, 7, 3] values =[110, 120, 2] capacity =10과 같으면 출력은 178이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

해상도 :=0
- 가중치와 값으로 쌍 P의 목록을 만들고 가중치당 값을 기준으로 정렬
- P의 각 쌍에 대해 수행
  - ci 용량이 0이면
    - 루프에서 나오다
  - pair[0]> 용량이면
    - res :=res + 몫 (쌍[1] /(쌍[0] / 용량)
    - 용량 :=0
  - 그렇지 않으면 pair[0] <=capacity인 경우
    - res :=res + pair[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