Python에서 트럭에 실을 수 있는 최대 단위를 찾는 프로그램

<시간/>

boxTypes[i]에는 두 개의 요소[유형 i의 상자 수, 유형 i의 상자당 단위 수]가 포함된 boxTypes라는 2D 배열로 표시된 상자 세트가 있다고 가정합니다. 이제 우리는 또한 그 트럭에 실을 수 있는 최대 상자 수인 또 다른 값 k가 있습니다. 상자의 수가 k를 넘지 않는 한 트럭에 실을 상자를 선택할 수 있습니다. 트럭에 실을 수 있는 최대 총 유닛 수를 찾아야 합니다.

따라서 입력이 boxTypes =[[2,4],[3,3],[4,2]], k =6과 같으면 출력은 19가 됩니다.

유형 1의 상자 2개 및 각각 4개의 단위가 들어 있습니다.
유형 2의 상자 3개 및 각 상자에 3개의 단위가 들어 있습니다.
유형 3의 상자 4개 및 각 상자에 2개의 단위가 들어 있습니다.

k =6이므로 유형 1과 2의 모든 상자와 유형 3의 상자 하나만 선택할 수 있으므로 (2*4) + (3*3) + 2 =8 + 9 +2 =19개 항목이 있습니다. .

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

각 상자에 있는 항목 수에 따라 boxTypes 정렬
총계 :=0, 채우기 :=0
boxTypes의 각 i에 대해 수행
- 채우기 + i[0] <=k인 경우
  - 채우기 :=채우기 + i[0]
  - 총계 :=총계 + i[0] * i[1]
- 그렇지 않으면
  - 총계 :=총계 + (k - 채우기) * i[1]
  - 루프에서 나오다
총 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(boxTypes, k):
   boxTypes.sort(key = lambda x : x[1], reverse = True)
   total = 0
   fill = 0
   for i in boxTypes:
      if fill + i[0] <= k:
         fill += i[0]
         total += i[0] * i[1]
      else:
         total += (k - fill) * i[1]
         break
   return total

boxTypes = [[2,4],[3,3],[4,2]]
k = 6
print(solve(boxTypes, k))

입력

[[2,4],[3,3],[4,2]], 6