배낭 무력 프로그램의 의미 만들기

Question

나는 이해하고 싶은 친구가 배낭 무차별 대원 프로그램을 받았다.

if (wt[n - 1] > W): 
return knapSack(W, wt, val, n - 1) 

을 아니다 나는 이것이 어떻게 작동하는지 이해한다 :

def knapSack(W, wt, val, n): 

    if n == 0 or W == 0: 
     return 0 


    if (wt[n - 1] > W): 
     return knapSack(W, wt, val, n - 1) 


    else: 
     return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), 
       knapSack(W, wt, val, n - 1)) 




values = [10, 500, 786] 
wt = [1, 2, 0.5] 
weight = 2 
n = len(values) 
print(knapSack(weight , wt, values, n)) 

나는 이것이 어떻게 작동하는지 이해하지 않는다 :

else: 
    return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), 
       knapSack(W, wt, val, n - 1)) 

을 TBH 내가이야 이건 내가 주어진 코드입니다 이 두 라인이 어떻게 작동하는지에 대한 단서가없는, 그들은 배낭을 무작위로 호출하는 것처럼 보입니다. 나는 또한 n-1이 무엇을하는지 이해하지 못한다. 내가 :)

Answer 1

배낭 문제의 기초 미안의 매우 모호한 요청을 알고

같은 것입니다 : 값과 무게 항목, 각각의 집합을 감안할 때, 아래 항목의 가장 가치있는 조합을 찾기 주어진 무게 한계.

다음은 문제의 변수입니다 (친구의 이름 지정 규칙은 매우 나쁨).

어떻게 프로그램 주소이 남아

없음 체중을 나머지

1. 항목 없음 :

   이 문제에 두 개의 터미널 경우가있다?

   if n == 0 or W == 0: 
        return 0 
   

   번째 코드 블록이 다른 경우가

   무게 제한 항목

   if (wt[n - 1] > W): 
        return knapSack(W, wt, val, n - 1) 
   

   이것은 단지 현재 테스트 제거되는 항목 배낭 알고리즘의 또 다른 반복을 시도하는 수단

   테스트중인 초과 .

   여기에 다른 블록이 실제로 무슨 말을

   무게 제한 항목을 초과하지 않는 퍼즐의 마지막 조각이

   else: 
       return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), 
         knapSack(W, wt, val, n - 1)) 
   

   을 테스트중인입니까? (왕복 중량 [N-1]의 일부) 및 제외 항목 (ㄱ 낮은 무게 제한 다시 배낭 알고리즘을 수행

   1. 현재 항목의 값이 + 값 : 두 가지 옵션 중 최대 값을 리턴 n-1 부분).

   2. 현재 항목이 제외되고 무게 제한이 동일한 배낭 알고리즘 (현재 항목이 무겁지 만별로 가치가없는 경우는이 옵션이 더 높을 것으로 생각 함).당신은 본질적에 추가,이 항목의 값을 무게를 조정하고, 최고의 남아있는 콤보가 무엇인지 확인하거나이 항목을 포함하지 않으며, 참조 말을하고 있기 때문에

   이

   는 어떤 작품 최고 나머지 콤보가 있습니다. 가능한 모든 하위 옵션 조합을 테스트합니다.

   이 모든 것은 Dynamic Programming으로 알려진 패러다임의 한 예입니다. 나는이 문제와 유사한 몇 가지 간단한 예제를 위해 그것에 대해 읽어 볼 것을 제안합니다. 일단 이러한 문제에 접근하기위한 방법을 찾으면 이해하는 것이 훨씬 쉬워집니다.