소개

0-1 배낭 문제는 배낭 문제의 일종으로 동적 프로그래밍 방식을 이해하는 데 사용됩니다. 형제인 fractional knapsack과 달리, greedy는 이 문제에 대한 최적의 솔루션을 보장하지 않습니다. 동적 프로그래밍을 사용하여 해결됩니다. 여기서 우리는 물건을 집어들거나 그냥 둘 수 있습니다. 물체의 일부를 선택할 수 없습니다.

문제 설명

가중치와 관련 값을 가진 n개의 객체가 주어졌다고 가정합니다. 용량 = maxWeight인 배낭도 제공됩니다. 우리의 목표는 maxWeight를 초과하지 않는다는 점을 염두에 두면서 가장 가치가 높고 가중치가 가장 적은 개체를 선택하여 이러한 개체에서 최대 이익을 얻는 것입니다. 각 개체는 한 번만 선택하거나 전혀 선택하지 않을 수 있습니다.

예를 들어 :

Input:
n=4
maxWeight=5
weights={4,3,5,1}
value={1,2,2,3}

Output:
5

이 경우 가중치가 3과 1이고 값이 2와 3인 개체의 총 값은 5입니다. 이것이 최대값입니다.

관찰

여기서 중요한 관찰은 무게 합계가 배낭의 용량보다 작거나 같고 최대 값 합계를 갖는 가중치의 하위 집합을 찾아야 한다는 것입니다.

욕심쟁이가 아닌 이유는 무엇입니까?

Greedy는 분수 배낭에 대해 작동하지만 0-1 배낭에 대해서는 작동하지 않습니다. 다음은 0-1 배낭에 대한 욕심 많은 접근 방식을 반증하는 예입니다. W=6이고 항목이 다음과 같다고 가정합니다.

Item   Value   Size   Value/Size
A       5.5       4         1.38
B       4          3         1.33
C       4          3         1.33

0-1 배낭의 경우 욕심 많은 접근 방식을 적용하면 가치/크기가 가장 높은 항목을 선택합니다. 항목 A. A의 크기가 4이므로 남은 공간은 2뿐입니다. 이제 더 이상 항목을 선택할 수 없습니다. 즉, 가방에 있는 유일한 물건은 총 가치 22인 품목 A뿐입니다.

반면에 욕심을 부리지 않고 가장 값진 물건을 가져가서 물건 B를 가져갔다면 물건 C도 가져갈 여유가 생겼을 것입니다. 이렇게 하면 가방에 있는 총 값이 24가 되므로 탐욕스러운 경로보다 낫습니다.

동적 접근

최종 답을 계산하는 데 도움이 되는 더 작은 하위 문제에 대한 솔루션을 저장하기 위해 2D 배열을 사용할 것입니다. 여기에서 재귀 접근 방식에 명시된 것과 동일한 두 가지 작업을 수행합니다.

물체를 집으십시오

i(번째) 개체를 선택하기로 결정하면 이익은 해당 개체의 가치 + 나머지 가중치에 대한 최적화된 답변이 됩니다. 값[i] + dp[i-1][c-무게[i]]

개체를 떠나

우리가 객체를 떠나기로 결정하면 이익은 그 가중치에 대한 최적화된 답변이 될 것입니다. dp[i-1][c]

특정 개체에 대한 답은 이 두 값의 최대값이 됩니다.

주요 조건:

dp[i][c] = max (dp[i-1][c], profits[i] + dp[i-1][c-weights[i]]);

int knapsack(int v[], int w[], int n, int W)
{
    int T[n+1][W+1];
    for (int j = 0; j <= W; j++) {
        T[0][j] = 0;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            if (w[i-1] > j) {
                T[i][j] = T[i-1][j];
            }
            else {
                T[i][j] = max(T[i-1][j], T[i-1][j-w[i-1]] + v[i-1]);
            }
        }
    }
    return T[n][W];
}

시간 복잡도 : O(n*W).\
공간 복잡도 : O(n*W). 추가 공간으로 2-d 배열 T를 사용했습니다.