배낭 파이썬 함수

Question

배낭 문제와 관련된이 질문은 배낭 문제의 결과와 거의 비슷합니다. 질문 :

당신이 N 항목의 컬렉션을 가지고 가정하자. 모든 항목의 무게가 같고, ,이며, 각 항목의 최대 값은 입니다.입니다. 입력으로서 배낭의 용량을 부여 파이썬 함수, 용량, 값 (오름차순으로 정렬) 목록 값, 각 항목과 중량와트 작성하고 을 반환 배낭이 지닐 수있는 최대 값은입니다.

필자는 함수를 쓰려고했지만 어쨌든 코드의 행에 적당한 숫자 인 w이 어디 있는지 알 수 없었습니다.

def knapsack(capacity,n): 
    if len(n) ==0: 
      return 0 
    elif n[-1][0] > capacity: 
      return knapsack(capacity, n[:-1]) 
    else: 
      return max(knapsack(capacity,n[:-1]), knapsack(capacity-n[-1][0],n[:-1]+n[-1][1] 

어떻게 든, 나는 파이썬 비교적 새로운 해요으로이 질문을 알아낼 수있는 방법을 많이 검색,하지만 난 완전히 질문을 파악하지 않은 것처럼 코드가 작동하는 방식을 좋아하지 않았다 . 이 Python 함수를 해결할 더 좋은 방법이 있습니까?

Answer 1

모두 무게가 같으면 문제가 아주 간단합니다.

값을 내림차순으로 정렬하고 값 목록에 더 이상 항목이 없거나 더 많은 항목을 저장할 수있을 때까지 목록에서 항목을 선택하기 만하면됩니다.

값이 오름차순으로 정렬된다는 점에 유의하십시오. 목록이 이미 오름차순으로 정렬되었으므로 항목을 값의 내림차순으로 표시되도록 목록을 간단히 되돌릴 수 있습니다. 이렇게하면 가장 큰 가치가있는 항목이 먼저 표시됩니다.

첫 번째 항목부터 시작하여 더 이상 배낭에 넣을 수 없을 때까지 항목을 계속 선택하십시오.

def knapsack(capacity, values): 
    values.reverse() 
    num_items = capacity // w 
    return sum(values[:num_items]) 

num_items에는 배낭에 넣을 수있는 최대 항목 수가 있습니다. values[:num_items] 배열 배열에서 최대 값 num_items 값을 검색하고, 마지막으로이 값을 sum 함수에 전달하여 최대 합계를 계산합니다.