피야 해적을 도와 가방 문제를 해결하자!

| View Solution on GitHub |

해적과 그의 전리품 사이에는 그런 사랑이 없다.(사진: ThoughtCo)
격리가 시작되었을 때 모든 과학 기술 회사가 격리에서 멀어져야 했던 것을 기억하십니까?우리 처음 몇 달 동안의 즐거움...줌에서 새로운 악작극 배우기!우리 반 학생들은 내가 나의 비활동 화면 이름을 Pierre the Py Pirate로 바꾼 것을 기억할 것이다.갑작스러운'헤이!'만큼 SQL 모델에 관한 강좌를 끊을 수 있는 것은 없다줌 채팅에서 온 Pierre.우리는 그 수업에서 매우 즐겁게 놀았다.
이것은 내가 피에르가 좋아할 것이라고 생각하는 문제이다. 왜냐하면 그는 해적이기 때문에 해적 사업에 종사하기 때문이다.어디 보자.

# A thief finds much more loot than he can fit in his knapsack.

기다리다피에르가 이해할 수 있는 방식으로 다시 쓰겠습니다.

# Pierre the Py Pirate has plundered new booty! But alas, he
# can only fit a limited amount in the cargo hold of his ship.
# Help him to find the most valuable combination of items 
# assuming that any fraction of a loot item can be kept.

1. 설정

예를 들어, 이 문제에 대해 우리는 두 개의 수조를 제시했다. 하나는 모든 항목의 권중이고, 다른 하나는 모든 값이다.우리는 화물칸의 용량도 얻었다.충분히 간단하다.다음 방법을 설정합니다.

def knapsack(cap, values, weights):
    pass

2. 전략

네가 피에르라면 이 문제를 어떻게 처리할지 생각해 봐.예를 들어 그는 다이아몬드 반지 하나를 발견했는데 무게는 매우 가볍지만 가치는 매우 높고 밀가루 한 포대가 있는데 무게는 매우 무겁지만 가치는 높지 않다.그는 먼저 반지를 보존한 후에 남은 공간을 채울 수 있는 밀가루를 보존하려고 한다.따라서 우리는 우선 무게의 가치에 따라 물품을 정렬한 다음에 우리의 용량에 도달할 때까지 가장 가치 있는 물품을 첨가할 것이다.

3. 아이템 리스트 정리

우선 정렬된 항목 목록을 놓을 새 items 목록을 만들 것입니다.그리고 우리는 values 목록 (또는 weights 목록을 순환할 것이다. 왜냐하면 그것들의 길이가 같기 때문이다.각 항목에 대해 각 항목의 값을 vpw로 저장하고 무게도 유지합니다(나중에 자세히 설명합니다).

def knapsack(cap, values, weights):
  items = []
  for i in range(len(values)):
    itemInfo = {
      'vpw': values[i]/weights[i],
      'weight': weights[i]
    }

다음에 우리는 이 항목을 items 목록에 추가해야 한다.그러나, 우리는 그것을 마지막에만 박을 수 없다. 이것은 vpw 순서에 따른 정렬 목록이다.따라서 우리는 items 목록을 훑어보고 현재 항목의 검사 개수vpw를 대조하여 어디에 두어야 하는지 볼 것이다.
우선 목록에 항목이 없으면 검사할 것이 없기 때문에 추가하기만 하면 됩니다.

    if len(items) == 0:
      items.append(itemInfo)

다음에 우리는 목록을 두루 훑어보았다.현재 항목vpw이 목록에 있는 항목보다 적으면 이동의 정확한 횟수를 알 수 없습니다.하나while 순환이 잘 될 거예요.

    else:
      k = 0
      while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
        k += 1

알겠습니다. 현재 우리의 색인 k 은 새로운 항목이 가야 할 곳을 가리켜야 합니다.우리는 파이톤insert() 방법을 사용하여 그것을 거기에 놓을 수 있다.

    else:
      k = 0
      while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
        k += 1
      items.insert(k, itemInfo)

4. 정렬 목록의 항목을 가방에 추가

이제 피에르의 화물칸을 채울 때가 됐어.앞에서 말한 바와 같이, 우리는 우리의 물품 명세서를 훑어보고, 우리의 용량이 가득 찰 때까지 편리하게 무게의 최대치에서 최소치까지 순서를 정하고, 모든 물품을 더할 것이다.
새로운 변수를 만들어 봅시다.total 우리가 돌려줘야 할 피에르 전리품의 최종 가치다.또한 프로젝트를 추가한 후 남은 용량을 추적하기 위해 cap_left 변수를 만들 것입니다.

  total = 0
  cap_left = cap

이제 우리는 이 항목들을 순환해서 훑어볼 것이다.

  for item in items:

모든 항목에 대해 우리는 우선 그것이 적합한지 검사할 것이다.만약 그렇다면, 우리는 그것의 값을 total 에 덧붙일 수 있다. (이 값은 항목 weight 을 곱해서 vpw 얻을 수 있다.무게를 cap_left에서 빼는 것을 잊지 마라!

if cap_left - item['weight'] >= 0 :
  total += item['weight'] * item['vpw']
  cap_left -= item['weight']

가령 우리가 이미 일부 항목을 추가했지만, 여전히 공간이 있지만, 다음 완전한 항목을 추가하기에는 부족하다.항목의 일부분을 추가할 수 있다는 힌트!이를 위해 우리는 남은 용량이 있는지 확인한 다음에 총량에 추가할 용량을 계산하기만 하면 된다.그중에 몇몇 수학 문제가 관련되어 있다.기본적으로 우리는 물품의 vpw에 잉여 용량을 곱한다.그리고 우리가 그것을 총수에 추가한 후에 cap_left는 0으로 설정해야 한다.

    elif cap_left > 0:
      total += item['vpw'] * cap_left
      cap_left = 0

나머지는return total!총:

def knapsack(cap, values, weights):
  items = []
  for i in range(len(values)):
    itemInfo = {
      'vpw': values[i]/weights[i],
      'weight': weights[i]
    }
    if len(items) == 0:
      items.append(itemInfo)
    else:
      k = 0
      while k < len(items) and items[k]['vpw'] > itemInfo['vpw']:
        k += 1
      items.insert(k, itemInfo)
  total = 0
  cap_left = cap
  for item in items:
    if cap_left - item['weight'] >= 0 :
      total += item['weight'] * item['vpw']
      cap_left -= item['weight']
    elif cap_left > 0:
      total += item['vpw'] * cap_left
      cap_left = 0
  return total

5. 해보기

피에르가 럼주 한 통, 밀가루 한 포대, 비단 한 권을 약탈했다고 가정해 보자.그의 배에는 60파운드의 공간이 있다.

cap = 60
values = [60, 100, 120]
weights = [20, 50, 30]

print(knapsack(cap, values, weights))

비단의 VPW가 가장 높고 4금/파운드이며 럼주가 3금/파운드, 밀가루가 2금/파운드이다.먼저 비단을 넣고 럼주를 넣고 마지막에 10파운드를 남겨 밀가루를 담는다.10파운드의 밀가루의 가치는 20골드이기 때문에 모두 200골드를 반품할 수 있다.예!
이 문제를 해결할 수 있는 많은 방법이 있다.만약 당신이 더 좋은 방법을 찾았다고 생각한다면, 평론에서 나에게 알려주세요.
| View Solution on GitHub |
Sheamus Heikkila는 대회에서 조교로 일했다.이 블로그는 GA와 무관합니다.