0/1 배리에이션 해결하기 배낭 (각 항목은 여러 소스 중 하나에서 선택 가능)

Question

연습 질문의 경우 0/당신이 i = 16을 선택하면, n = 10을위한 .. 즉

,

S1={(d_k, b_k) | 1 ≤ k ≤ n}, 
S2={(d_k, b_k) | n + 1 ≤ k ≤ 2n}, 
S3={(d_k, b_k) | 2n + 1 ≤ k ≤ 3n}, 
S4 = {(d_k, b_k) | 3n + 1 ≤ k ≤ 4n} 

1 배낭 문제는 ... 기본적으로 각 항목은 4 가지 소스에서 온다, 그 항목은 소스의 한에서 취할 수 있습니다 넣으십시오. 즉, 선택하지 말아야합니다. 6, 26 or 36 ...

이 문제를 해결하고 반복 방정식을 고안하는 데 도움을 줄 수 있습니까?

Answer 1

우리는 4N 요소를 가지고있다.

표기법

• V[k] - 소자 (k)의 값 (1 < = K < = 4N)
• W[k] - 소자 (k)의 가중치 (1 < = K < = 4N)
• B - 바운드
• f(k,B) - 바운드가 B이고 최적 해의 값은 다음과 같습니다. 4k 요소.
  1. 는 배낭에 k 번째 요소를 삽입하지 : k 번째 요소에 대해

우리는 다섯 개 가지 선택이있다. 이 제약 하에서, 최적 솔루션의 값은 f(k-1,B)입니다. 왜? 왜냐하면 우리는 k-1 개의 더 많은 원소를 가지고 있고 그 경계는 여전히 B이기 때문입니다.

S1에서 k 번째 원소를 취합니다. 이 제약 조건 하에서 최적 솔루션의 값은 V[k] + f(k-1, B - W[k])입니다. 왜? 우리는 k 번째 원소에 대해 V [k]를 얻었고 W [k]를 허리에 묶었습니다. 나머지 요소들에 대해서는 f (k-1, B - W [k])를 얻습니다.

S2에서 k 번째 요소 가져 오기. 이전과 동일한 로직을 사용하여 해당 제약 조건에서 최적 솔루션의 값이 V[k+n] + f(k-1, B - W[k+n])임을 확인하십시오.

S3에서 n 번째 요소를 가져옵니다. 최적 : V[k+2n] + f(k-1, B - W[k+2n]).

S4에서 n 번째 요소 가져 오기.최적 : V[k+3n] + f(k-1, B - W[k+3n]).

귀하의 목표는 f를 최대화하는 것입니다. 따라서 재발 방정식은 다음과는

f(k, B) = 
    max { 
     f(k-1,B),      //you don't take item n 
     V[k] + f(k-1, B - W[k]), //you take item k from S1 
     V[k+n] + f(k-1, B - W[k+n]), //you take item k from S2 
     V[k+2n] + f(k-1, B - W[k+2n]), //you take item k from S3 
     V[k+3n] + f(k-1, B - W[k+3n]) //you take item k from S2 
    } 

초기 조건을 찾기 위해 무엇 왼쪽입니다.

Answer 2

표준 0/1 배낭 문제 : 각 항목에 대해 사용자가 가져 가지 않거나 사용자가 수행하지 않습니다.

귀하의 문제 : 각 항목에 대한 , 중 당신이 그것을하지 않거나 소스 1에서 그것을 가지고, 또는 ... 또는 당신이보고 이제 4

소스에서 가져 0/1 배낭 문제에 대한 일반적인 동적 프로그래밍 알고리즘과 반복 관계. 재발 관계에있는 RHS의 각 비트가 어디서 오는 지 살펴보십시오. 위의 첫 번째 문장에 해당합니다. 위의 두 번째 구문을 대신 사용하십시오.

(나는 조금 애매되고있어 경우,이 숙제는 당신이 :-)를 배우는 의미있는 때문입니다.)