동적 프로그래밍 예제를 사용한 0/1 배낭 문제 해결
사라 첸
배낭 문제란 무엇인가?
배낭 문제 알고리즘은 조합론에서 매우 유용한 문제입니다. 슈퍼마켓에는 n개의 꾸러미(n ≤ 100)가 있습니다. 꾸러미 i의 무게는 W[i] ≤ 100이고 값은 V[i] ≤ 100입니다. 도둑이 슈퍼마켓에 침입하여 M(M ≤ 100)을 초과하는 무게를 운반할 수 없습니다. ). 여기서 해결해야 할 문제는 도둑이 가장 높은 가치를 얻기 위해 어떤 패키지를 가져갈 것인가입니다.
입력:
- 최대 중량 M 및 패키지 수 n.
- 가중치 W[i]와 해당 값 V[i]의 배열.
출력:
- 용량의 가치와 그에 상응하는 무게를 극대화합니다.
- 도둑이 가져갈 패키지는 무엇입니까?
배낭 알고리즘은 두 가지 유형으로 더 나눌 수 있습니다.
- 동적 프로그래밍을 사용한 0/1 배낭 문제. 이 Knapsack 알고리즘 유형에서는 각 패키지를 가져갈 수도 있고 가져오지 않을 수도 있습니다. 게다가 도둑은 가져간 패키지의 일부만 가져갈 수도 없고 패키지를 두 번 이상 가져갈 수도 없습니다. 이 유형은 동적 프로그래밍 접근 방식으로 해결할 수 있습니다.
- 분수 배낭 문제 알고리즘. 이런 유형은 Greedy Strategy로 해결할 수 있습니다.
예제와 함께 동적 프로그래밍을 사용하여 배낭 문제를 해결하는 방법
분할 정복 전략에서는 해결해야 할 문제를 하위 문제로 나눕니다. 하위 문제는 더 작은 하위 문제로 세분화됩니다. 이 작업은 쉽게 해결할 수 있는 하위 문제가 나타날 때까지 계속됩니다. 그러나 이러한 분할 과정에서 동일한 문제에 여러 번 직면하게 될 수도 있습니다.
Knapsack 동적 프로그래밍의 기본 아이디어는 해결된 하위 문제의 솔루션을 저장하는 테이블을 사용하는 것입니다. 하위 문제에 다시 직면하면 다시 해결할 필요 없이 테이블에서 솔루션을 가져오기만 하면 됩니다. 따라서 동적 프로그래밍으로 설계된 알고리즘은 매우 효과적입니다.
동적 프로그래밍으로 문제를 해결하려면 다음 작업을 수행해야 합니다.
- 가장 작은 하위 문제의 해결책을 찾으십시오.
- 가장 작은 하위 문제의 해를 통해 하위 문제의 해를 구축하는 공식(또는 규칙)을 알아보세요.
- 하위 문제의 솔루션을 저장하는 테이블을 만듭니다. 그런 다음 찾은 공식에 따라 하위 문제의 해를 계산하고 테이블에 저장합니다.
- 해결된 하위 문제에서 원래 문제의 해결책을 찾습니다.
0/1 배낭 문제 분석
동적 프로그래밍을 이용하여 0/1 배낭 문제를 분석해보면 몇 가지 눈에 띄는 점을 발견할 수 있습니다. 배낭 알고리즘의 값은 두 가지 요소에 따라 달라집니다.
- 고려 중인 패키지 수
- 배낭이 보관할 수 있는 남은 무게입니다.
따라서 두 가지 가변 수량을 갖게 됩니다.
동적 프로그래밍을 사용하면 다음과 같은 유용한 정보를 얻을 수 있습니다.
- 목적 함수는 두 가지 가변 수량에 따라 달라집니다.
- 옵션 테이블은 2차원 테이블이 됩니다.
B[i][j]를 호출하면 가중치 제한이 j인 패키지 {1, 2, …, i}에서 선택하여 가능한 최대 값이 됩니다.
- 무게 제한이 M인 n개의 패키지에서 선택했을 때의 최대값은 B[n][M]입니다. 즉, 선택할 수 있는 패키지가 i개일 때, 배낭의 최대 무게가 j일 때 B[i][j]가 최적의 무게입니다.
- 최적의 가중치는 항상 최대 가중치(B[i][j] ≤ j)보다 작거나 같습니다.
예: B[4][10] = 8. 이는 선택할 수 있는 첫 번째 패키지가 8개(4~1번째 패키지)이고 최대 중량이 있을 때 최적의 경우 선택한 패키지의 총 중량이 4임을 의미합니다. 배낭의 개수는 10개입니다. 4개 항목을 모두 선택할 필요는 없습니다.
B[i][j] 계산 공식
입력하면 다음을 정의합니다.
- W[i], V[i]는 차례로 패키지 i의 무게와 가치입니다.
![B[i][j] 계산 공식](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%2016%2023'%3E%3C/svg%3E)
{1, …, n}. - M은 배낭이 지닐 수 있는 최대 무게입니다.
![B[i][j] 계산 공식](https://www.guru99.com/images/1/043019_0611_KnapsackPro4.png){kind=small}
{1, …, n}.단순히 1개의 패키지만 선택할 경우. 모든 j에 대해 B[1][j]를 계산합니다. 이는 배낭의 최대 무게 ≥ 첫 번째 패키지의 무게를 의미합니다.
B[1][j] = W[1]
무게 제한 j를 사용하면 패키지 {1, 2, …, i – 1, i} 중에서 가장 큰 값을 갖는 최적의 선택에는 두 가지 가능성이 있습니다.
- 패키지 i를 선택하지 않은 경우 B[i][j]는 무게 제한이 j인 패키지 {1, 2, …, i – 1} 중에서 선택하여 가능한 최대 값입니다. 당신은:
B[i][j] = B[i – 1][j]
- 패키지 i가 선택되면(물론 W[i] ≤ j인 경우만 고려) B[i][j]는 패키지 i의 V[i] 값에 더해 다음 중 하나를 선택하여 최대값을 얻을 수 있습니다. 무게 제한(j – W[i])이 있는 패키지 {1, 2, …, i – 1}. 즉, 귀하가 보유한 가치 측면에서 다음과 같습니다.
B[i][j] = V[i] + B[i – 1][j – W[i]]
가능한 최대값인 B[i][j]가 생성되므로 B[i][j]는 위 2개의 값 중 최대값이 됩니다.
동적 프로그래밍의 기초
따라서 패키지 i를 선택하는 것이 더 나은지 여부를 고려해야 합니다. 거기에서 다음과 같은 재귀 수식이 있습니다.
B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]
B[0][j] = 0 패키지 = 0 중에서 선택하여 가능한 최대값을 쉽게 알 수 있습니다.
옵션 표 계산
위의 재귀 공식을 기반으로 옵션 테이블을 작성합니다. 결과가 올바른지 확인하려면(정확하지 않은 경우 목적 함수 B[i][j]를 다시 작성합니다). 목적 함수 B[i][j]와 옵션 테이블을 생성하여 추적 방향을 정할 수 있습니다.
옵션 B 테이블에는 n + 1개 라인, M + 1개 열,
- 첫째, 동적 프로그래밍의 기초로 채워집니다. 0행에는 모두 XNUMX이 포함됩니다.
- 재귀 공식을 사용하여 라인 0을 사용하여 라인 1을 계산하고 라인 1을 사용하여 라인 2를 계산합니다. 모든 라인이 계산될 때까지.
더듬다
옵션 테이블을 계산할 때 무게 제한이 M인 n개의 패키지를 모두 선택할 때 얻은 최대값인 B[n][M]에 관심이 있습니다.
- If B[n][M] = B[n – 1][M] 패키지 n이 선택되지 않은 경우 B[n – 1][M]을 추적합니다.
- If B[n][M] ≠ B[n – 1][M], 최적의 선택에는 패키지 n과 트레이스 B[n – 1][M – W[n]]이 있음을 알 수 있습니다.
옵션 테이블의 행 0에 도달할 때까지 계속 추적합니다.
선택한 패키지를 찾기 위해 옵션 테이블을 조회하는 알고리즘
참고: B[i][j] = B[i – 1][j]인 경우 패키지 i가 선택되지 않습니다. B[n][W]는 배낭에 담긴 최적의 패키지 총 가치입니다.
추적 단계:
- 1단계: i = n부터 시작하여 j = M입니다.
- 2단계: j열을 보면 맨 아래부터 위로 B[i][j] > B[i – 1][j]와 같은 라인 i가 있습니다. 선택한 패키지 i를 표시합니다. [i] = true를 선택합니다.
- 3단계: j = B[i][j] – W[i]. j > 0이면 2단계로 이동하고, 그렇지 않으면 4단계로 이동합니다.
- 4단계: 옵션 표에 따라 선택한 패키지를 인쇄합니다.
Java 암호
public void knapsackDyProg(int W[], int V[], int M, int n) {
int B[][] = new int[n + 1][M + 1];
for (int i=0; i<=n; i++)
for (int j=0; j<=M; j++) {
B[i][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= M; j++) {
B[i][j] = B[i - 1][j];
if ((j >= W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
}
System.out.print(B[i][j] + " ");
}
System.out.print("\n");
}
System.out.println("Max Value:\t" + B[n][M]);
System.out.println("Selected Packs: ");
while (n != 0) {
if (B[n][M] != B[n - 1][M]) {
System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
M = M - W[n-1];
}
n--;
}
}
배낭 코드 설명:
- 테이블 B[][]를 생성합니다. 각 셀의 기본값은 0으로 설정됩니다.
- 상향식 방식으로 테이블 B[][]를 빌드합니다. 검색 공식을 사용하여 옵션 테이블을 계산합니다.
- B[i][j]를 계산합니다. 패키지를 선택하지 않은 경우 i.
- 그런 다음 평가하십시오. 패키지 i를 선택하면 B[i][j]를 재설정하는 것이 더 유리할 것입니다.
- n행부터 0행까지 테이블을 추적합니다.
- 패키지 n을 선택하는 경우 패키지 n을 선택하면 가중치 M – W[n – 1]만 추가할 수 있습니다.
이 튜토리얼에는 두 가지 예가 있습니다. 다음은 두 가지 예와 함께 위 프로그램을 실행하는 Java 코드입니다.
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{3, 4, 5, 9, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{3, 4, 4, 10, 4};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 11;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackDyProg(W, V, M, n);
}
출력은 다음과 같습니다.
- 첫 번째 예:
0 0 0 3 3 3 3 3 3 3 3 3 0 0 0 3 4 4 4 7 7 7 7 7 0 0 0 3 4 4 4 7 7 8 8 8 0 0 0 3 4 4 4 7 7 10 10 10 0 0 0 3 4 4 4 7 8 10 10 11 Max Value: 11 Selected Packs: Package 5 with W = 4 and Value = 4 Package 2 with W = 4 and Value = 4 Package 1 with W = 3 and Value = 3
- 두 번째 예:
0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15 Max Value: 15 Selected Packs: Package 5 with W = 4 and Value = 10 Package 4 with W = 1 and Value = 2 Package 3 with W = 1 and Value = 1 Package 2 with W = 2 and Value = 2
