동적 프로그래밍 예제를 사용한 0/1 배낭 문제 해결

배낭 문제란 무엇인가?

The 배낭 문제 이는 전형적인 조합 최적화 문제입니다. 슈퍼마켓은 여러 개의 매장을 운영합니다. n 패키지(n ≤ 100). 패키지 i 각 소포는 무게가 W[i] ≤ 100이고 가치가 V[i] ≤ 100입니다. 도둑은 최대 허용 무게 M(M ≤ 100)을 초과하는 무게를 운반할 수 없습니다. 도둑은 총 가치를 최대화하기 위해 어떤 소포들을 가져가야 할까요?

입력:

• 최대 중량 M 및 패키지 수 n.
• 가중치 W[i]와 해당 값 V[i]의 배열.

출력:

• 용량 범위 내에서 얻을 수 있는 최대 총 가치.
• 도둑이 가져가야 할 정확한 소포 목록.

배낭 알고리즘은 두 가지 잘 알려진 변형으로 나뉩니다.

• 0/1 배낭 문제 동적 프로그래밍으로 해결했습니다. 각 패키지는 전체를 가져가거나 남겨두거나 둘 중 하나이며, 부분적인 조각이나 중복된 것은 없습니다.
• 분수 배낭 문제 탐욕 전략으로 해결했습니다. 여기서는 남은 용량을 채우기 위해 패키지의 일부를 가져갈 수 있습니다.

예제와 함께 동적 프로그래밍을 사용하여 배낭 문제를 해결하는 방법

분할 정복은 큰 문제를 하위 문제로 나누고, 각 하위 문제가 쉬워질 때까지 계속해서 분할하는 방식입니다. 하지만 단순 재귀는 같은 하위 문제를 여러 번 해결하게 되어 작업량을 낭비하는 경우가 많습니다.

배낭 동적 프로그래밍의 핵심 아이디어는 해결된 모든 하위 문제를 테이블에 저장하는 것입니다. 반복 호출 시 재계산을 수행하는 대신 답을 읽어오므로 지수 시간 복잡도를 갖는 재귀 호출이 다항 시간 복잡도를 갖는 코드로 변환됩니다.

동적 프로그래밍을 사용하여 배낭 문제 해결

동적 프로그래밍 솔루션을 설계하려면 다음 네 단계를 따릅니다.

• 가장 작은 하위 문제부터 먼저 해결하세요.
• 더 작은 문제들로부터 하위 문제에 대한 해답을 도출하는 점화식을 만드세요.
• 재귀 관계식을 이용하여 하향식으로 계산한 표에 하위 문제의 답을 저장합니다.
• 모든 항목이 입력된 표를 종합하여 최종 답을 구하세요.

0/1 배낭 문제 분석

최적값은 두 가지 독립적인 요인에 따라 달라집니다.

1. 현재 검토 중인 패키지는 몇 개입니까?
2. 배낭에 아직 실을 수 있는 무게가 남아 있습니다.

목적 함수가 두 가지 변수에 의존하기 때문에 선택지 표는 2차원이어야 합니다. B[i][j] 무게 제한 j를 갖는 패키지 {1, …, i} 중에서 선택할 때의 최댓값을 나타냅니다.

• 최종 답은 다음과 같습니다. B[n][M]용량 M 미만의 모든 n개 패키지 중에서 가장 우수한 총 가치를 제공합니다.
• 선택된 총 중량은 항상 현재 용량에 의해 제한됩니다. B[i][j] ≤ j.

예: B[4][10] = 8인 경우 용량 10 미만의 첫 네 개 패키지에서 가장 좋은 총 무게는 8입니다. 이 네 개 패키지 중 일부는 건너뛸 수 있습니다.

B[i][j] 계산 공식

• W[i], V[i] i는 패키지 i의 무게와 값이며, 여기서 i는 {1, …, n}입니다.
• M 배낭이 견딜 수 있는 최대 무게입니다.

하나의 패키지를 사용하는 기본 사례: 모든 용량 j ≥ W[1]에 대해:

B[1][j] = W[1]

일반적인 경우, 패키지 i를 용량 j에 포함할지 여부를 결정하십시오.

• 패키지 i가 건너 뛴, B[i][j]는 용량 j에서 패키지 {1, …, i-1}을 사용하여 얻은 최적값과 같습니다.

B[i][j] = B[i - 1][j]

• 패키지 i가 촬영 (W[i] ≤ j인 경우에만 허용됨), B[i][j]는 V[i]에 용량 j - W[i] 하에서 패키지 {1, …, i-1} 중 최적값을 더한 값과 같습니다.

B[i][j] = V[i] + B[i - 1][j - W[i]]

두 후보 중 더 큰 쪽을 선택하세요.

동적 프로그래밍의 기초

두 경우를 결합하면 완전한 재현율이 나타납니다.

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

기본 경우는 다음과 같습니다. B[0][j] = 0 모든 j에 대해, 왜냐하면 용량과 관계없이 패키지가 0개이면 가치가 0이기 때문입니다.

옵션 표 계산

반복문을 사용하여 B를 생성합니다. B가 채워지면 동일한 테이블이 다음 작업을 제어합니다. trac선택된 패키지를 재구성하는 e-back입니다. 표 B는 n + 1개의 행과 M + 1개의 열을 가지고 있습니다.

• 0번째 행은 기본 사례이며, 모든 행이 0으로 채워져 있습니다.
• 0번째 행을 사용하여 1번째 행을 계산하고, 1번째 행을 사용하여 2번째 행을 계산하는 식으로 n번째 행이 완료될 때까지 계속합니다.

옵션 표

Trace

B가 완료되면, 다음으로 넘어가세요. B[n][M]이는 용량 M을 가진 모든 n개 패키지에 걸쳐 최적의 총 가치입니다.

• If B[n][M] = B[n-1][M]패키지 n이 선택되지 않았으므로 계속 진행하십시오. tracB[n-1][M]에서 오는 ing.
• If B[n][M] ≠ B[n-1][M]패키지 n이 선택되었으므로 계속 진행하십시오. tracB[n-1][M – W[n]]에서 ing.

표의 0번째 행에 도달할 때까지 이 과정을 반복하십시오.

선택한 패키지를 찾기 위해 옵션 테이블을 조회하는 알고리즘

참고: 언제든지 B[i][j] = B[i-1][j]패키지 i가 선택되지 않았습니다. 값 B[n][M] 배낭에 담을 수 있는 최적의 총 가치입니다.

단계 trac선택한 패키지에 대해:

• 1 단계 : i = n, j = M에서 시작합니다.
• 2 단계 : 열 j를 아래에서 위로 스캔하여 B[i][j] > B[i-1][j]인 행 i를 찾습니다. 패키지 i를 선택된 것으로 표시합니다. Select[i] = true.
• 3 단계 : j = j – W[i]로 업데이트합니다. j > 0이면 2단계로 돌아가고, 그렇지 않으면 4단계로 이동합니다.
• 4 단계 : 선택됨으로 표시된 모든 패키지를 인쇄하십시오.

Java Code

다음 Java 이 메서드는 B[][]를 아래에서 위로 채우고, 검사를 위해 테이블을 출력한 다음, trac선택된 패키지입니다.

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: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

knapsackDyProg() 함수 Java

코드 설명:

1. 테이블 할당 B[][] 모든 셀을 0으로 초기화합니다.
2. 이전 섹션의 재귀식을 사용하여 B[][]를 아래에서 위로 채웁니다.
3. 각 셀을 "패키지 i 건너뛰기" 값으로 시작하세요. B[i-1][j].
4. 패키지 i를 선택하는 것이 가능하고 확실히 더 나은 가치를 제공한다면 해당 셀을 덮어씁니다.
5. Tracn번째 행에서 선택된 항목들을 0번째 행으로 되돌립니다.
6. 패키지 n이 선택될 때마다 남은 용량을 감소시킵니다. W[n-1].

수정 사항: 원래 코드 조각이 변형된 매개변수 M 읽는 동안 B[n][M]위의 더 안전한 버전은 별도의 커서를 사용합니다. j 위한 trace.

The Java 드라이버는 두 개의 예제를 사용하여 알고리즘을 실행합니다.

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    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

0/1 배낭 게임의 시간 및 공간 복잡성

• 시간 복잡도: O(n · M) — 두 개의 중첩된 루프는 n개의 항목을 M+1개의 용량 상태에 걸쳐 순환시킵니다.
• 공간 복잡성: 전체 표에 대해 O(n · M)의 시간이 소요되지만, kee를 사용하면 O(M)으로 줄일 수 있습니다.ping 이전 행만 trac전자후속료는 필요하지 않습니다.

실행 시간은 다음과 같습니다. 유사다항식M 값에 대해서는 다항식적이지만, M을 인코딩하는 데 사용되는 비트 수에 대해서는 지수적이다. 이것이 바로 동적 프로그래밍이 실제로 효율적임에도 불구하고 0/1 배낭 문제가 여전히 NP-난해 문제로 남아 있는 이유이다.

0/1 배낭 문제의 응용

• 중량 제한 내에서 화물 적재, 컨테이너 포장 및 창고 피킹 작업을 수행합니다.
• 고정 비용과 예상 수익률을 고려한 투자 프로젝트 전반에 걸친 예산 배분.
• 개별 부품을 분할할 수 없는 제조 공정에서의 절단 문제.
• 배낭난제에 기반한 머클-헬만과 같은 암호화 방식.
• 클라우드 컴퓨팅 환경에서 자원 제약 스케줄링 및 CPU 작업 배치.
• 고정된 특징 예산 하에서의 머신러닝 특징 선택.

자주 묻는 질문