kz-maxx

RU KZ
← Басты бет

Рюкзак задачасы

0/1 Knapsack: рекурсия, memoization, итеративный DP және memory optimization

Рюкзак задачасы деген не?

Рюкзак задачасы — динамикалық программалаудың классикалық задачасы.

Бізде n зат бар. Әр затта екі мән болады:

  • weight[i] — заттың weight-і
  • value[i] — заттың value-ы

Рюкзактың сыйымдылығы W. Кейбір заттарды таңдау керек:

жалпы weight ≤ W
жалпы value максималды болу керек
0/1 knapsack-та әр затты максимум бір рет ғана аламыз: не аламыз, не алмаймыз.

Қарапайым мысал

Рюкзак сыйымдылығы:

W = 5

Заттар:

Зат Weight Value
1 3 10
2 2 7
3 4 12

Ең жақсы таңдау:

1-затты және 2-затты алу
weight = 3 + 2 = 5
value = 10 + 7 = 17

Жауап: 

17

Негізгі идея

Әр зат үшін екі вариант бар:

  • затты алмау
  • егер орын жетсе, затты алу
answer = max(
  затты алмайтын вариант,
  затты алатын вариант
)

Рекурсивный метод

Алдымен рюкзакты рекурсия арқылы түсіну оңай.

Мына функцияны ойлаймыз: 

f(i, w)

Бұл алғашқы i затты қарағанда және рюкзакта w орын болғанда алуға болатын максималды value.

i — қанша зат қарастырамыз
w — рюкзактың қазіргі сыйымдылығы

Рекурсивный переход

i-ші затты қараймыз.

1-вариант: i-ші затты алмаймыз: 

f(i - 1, w)

2-вариант: i-ші затты аламыз. Бұл тек оның weight-і w-дан аспаса ғана болады. 

f(i - 1, w - weight[i]) + value[i]

Сондықтан формула: 

f(i, w) = max(f(i - 1, w), f(i - 1, w - weight[i]) + value[i]);

Базалық жағдай

Егер зат жоқ болса, value 0 болады. 

if (i == 0) {
    return 0;
}

Егер рюкзакта орын қалмаса, енді ештеңе ала алмаймыз. 

if (w == 0) {
    return 0;
}

Обычный рекурсия

int solve(int i, int w) {
    if (i == 0 || w == 0) {
        return 0;
    }

    int ans = solve(i - 1, w);

    if (weight[i] <= w) {
        ans = max(ans, solve(i - 1, w - weight[i]) + value[i]);
    }

    return ans;
}

Бұл код идея бойынша дұрыс, бірақ баяу. Себебі бірдей state-терді көп рет қайта есептейді.

Обычный рекурсия шамамен O(2ⁿ) жұмыс істеуі мүмкін, себебі әр затта екі вариант бар: алу немесе алмау.

Рекурсия + memoization

Бірдей state-ті қайта есептемеу үшін жауапты сақтаймыз: 

dp[i][w]

Бұл i, w state үшін answer.

Егер answer бұрын есептелген болса, оны қайтарамыз: 

if (dp[i][w] != -1) {
    return dp[i][w];
}

Рекурсия + memoization толық код

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const int M = 10010;

int n, W;
int weight[N];
int value[N];
int dp[N][M];

int solve(int i, int w) {
    if (i == 0 || w == 0) {
        return 0;
    }

    if (dp[i][w] != -1) {
        return dp[i][w];
    }

    int ans = solve(i - 1, w);

    if (weight[i] <= w) {
        ans = max(ans, solve(i - 1, w - weight[i]) + value[i]);
    }

    dp[i][w] = ans;
    return dp[i][w];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    memset(dp, -1, sizeof(dp));

    cout << solve(n, W);

    return 0;
}

Итеративный DP-ға қалай ауыстырамыз?

Рекурсияда: 

solve(i, w)

Итеративный DP-да: 

dp[i][w]

Мағынасы:

dp[i][w] = максималды value
алғашқы i затты қарастырғанда
рюкзак сыйымдылығы w болса

Базалық мәндер

Егер зат саны 0 болса, answer 0: 

dp[0][w] = 0;

Егер сыйымдылық 0 болса, answer 0: 

dp[i][0] = 0;

Глобальный массив C++-та өзі 0 болады, сондықтан көбіне бөлек жазбаса да болады.

Итеративный переход

Әр зат i және әр сыйымдылық w үшін:

Затты алмаймыз: 

dp[i][w] = dp[i - 1][w];

Егер затты алуға орын жетсе: 

dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i]] + value[i]);

2D DP толық реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const int M = 10010;

int n, W;
int weight[N];
int value[N];
int dp[N][M];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];

            if (weight[i] <= w) {
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i]] + value[i]);
            }
        }
    }

    cout << dp[n][W];

    return 0;
}

Input / Output мысалы

Input

3 5
3 10
2 7
4 12

Output

17

Мұнда:

1-зат: weight 3, value 10
2-зат: weight 2, value 7
3-зат: weight 4, value 12
W = 5

Ең жақсы таңдау — 1-зат және 2-зат.

dp[i][w] қалай оқылады?

Мысалы: 

dp[3][5]

Бұл дегеніміз:

алғашқы 3 затты қарастырдық
рюкзак сыйымдылығы 5
максималды қандай value ала аламыз?

Финал answer: 

dp[n][W]

Memory optimization

Формулада: 

dp[i][w]

тек алдыңғы строкаға байланысты: 

dp[i - 1][...]

Сондықтан бір ғана массив қолдануға болады: 

dp[w]

Мұнда dp[w] — сыйымдылық w үшін ең жақсы answer.

Неге цикл оңнан солға жүреді?

0/1 knapsack-та әр затты тек бір рет аламыз.

Сондықтан dp[w] жаңартқанда циклді оңнан солға жүргіземіз: 

for (int w = W; w >= weight[i]; w--)

Егер солдан оңға жүрсек, бір зат бірнеше рет қолданылып кетуі мүмкін.

0/1 knapsack үшін басты правило: weight бойынша цикл W-дан weight[i]-ге қарай төмен жүреді.

1D DP толық реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int n, W;
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;

        for (int w = W; w >= weight; w--) {
            dp[w] = max(dp[w], dp[w - weight] + value);
        }
    }

    cout << dp[W];

    return 0;
}

2D DP vs 1D DP

Метод Память Плюс Минус
2D DP O(nW) түсіну оңай память көп кетеді
1D DP O(W) память үнемдейді цикл бағыты маңызды

Қай заттар таңдалғанын табу

Кейде тек max value емес, нақты қай заттар алынғанын шығару керек.

Ол үшін 2D DP қолданған ыңғайлы.

Артқа қарай жүреміз:

i = n, w = W-дан бастаймыз
егер dp[i][w] == dp[i - 1][w], i-зат алынбаған
әйтпесе i-зат алынған

Заттарды қалпына келтіру коды

vector<int> items;
int w = W;

for (int i = n; i >= 1; i--) {
    if (dp[i][w] == dp[i - 1][w]) {
        continue;
    }

    items.push_back(i);
    w -= weight[i];
}

reverse(items.begin(), items.end());

Қалпына келтірумен толық код

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const int M = 10010;

int n, W;
int weight[N];
int value[N];
int dp[N][M];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];

            if (weight[i] <= w) {
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i]] + value[i]);
            }
        }
    }

    cout << "Max value: " << dp[n][W] << '\n';

    vector<int> items;
    int w = W;

    for (int i = n; i >= 1; i--) {
        if (dp[i][w] == dp[i - 1][w]) {
            continue;
        }

        items.push_back(i);
        w -= weight[i];
    }

    reverse(items.begin(), items.end());

    cout << "Items: ";

    for (int x : items) {
        cout << x << ' ';
    }

    return 0;
}

Unbounded Knapsack

Рюкзактың басқа түрі бар: әр затты қанша рет болса да алуға болады.

Бұл:

unbounded knapsack
полный рюкзак

Мұнда цикл weight бойынша солдан оңға жүреді: 

for (int w = weight; w <= W; w++)

Полный рюкзак реализация

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;

int n, W;
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> W;

    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;

        for (int w = weight; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - weight] + value);
        }
    }

    cout << dp[W];

    return 0;
}
0/1 knapsack: цикл оңнан солға. Unbounded knapsack: цикл солдан оңға.

0/1 vs полный рюкзак

Тип Затты неше рет алуға болады? w циклі
0/1 Knapsack 0 немесе 1 рет W-дан төмен
Unbounded Knapsack қанша рет болса да weight-тен жоғары

Типтік қателер

  • dp[i][w] нені білдіретінін түсінбеу
  • weight пен value-ды шатастыру
  • 0/1 knapsack-та циклді солдан оңға жүргізу
  • полный рюкзакта циклді оңнан солға жүргізу
  • weight[i] <= w тексеруді ұмыту
  • заттарды қалпына келтіруде 1D DP қолдануға тырысу
  • массив size-ын тым кішкентай қою

Асимптотика

Метод Уақыт Память
Обычный рекурсия O(2ⁿ) O(n)
Memoization O(nW) O(nW)
2D DP O(nW) O(nW)
1D DP O(nW) O(W)

Задачада қалай ойлау керек?

1. Зат деген не?
2. Weight деген не?
3. Value деген не?
4. Затты бір рет аламыз ба, көп рет аламыз ба?
5. Maximum, minimum немесе тәсіл саны керек пе?
6. W size қанша?
7. O(nW) жарай ма?

Қысқа шаблон 0/1 Knapsack

int dp[W + 1];

for (int i = 1; i <= n; i++) {
    cin >> weight >> value;

    for (int w = W; w >= weight; w--) {
        dp[w] = max(dp[w], dp[w - weight] + value);
    }
}

cout << dp[W];

Қысқа шаблон полного рюкзака

int dp[W + 1];

for (int i = 1; i <= n; i++) {
    cin >> weight >> value;

    for (int w = weight; w <= W; w++) {
        dp[w] = max(dp[w], dp[w - weight] + value);
    }
}

cout << dp[W];