0-1 ზურგჩანთის ამოცანა

რომელი ფუნქციები დაეტევა ამ სპრინტში, რომელი ფაილები ამ დისკზე, რომელი ტვირთი ამ მანქანაში: ქვესიმრავლის არჩევა ბიუჯეტის ფარგლებში ზურგჩანთის ამოცანაა. ზოგადად ის NP-სრულია, მაგრამ რეალისტური ტევადობისთვის მარტივი ცხრილი მას ზუსტად ხსნის.

★ ლექცია: DP_knapsack · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 20 წთ

←ეყრდნობა

7ზურგჩანთის უწყვეტი ამოცანაროცა ნივთის გაყოფა არ შეიძლება, ხარბი შეფარდება ცდება და ცხრილი გვჭირდება.10დპ ბადეზეზურგჩანთის ცხრილი ბადეა: ნივთები სტრიქონებად, ტევადობები სვეტებად.4ქვესიმრავლეებისა და გადანაცვლებების გენერაციაზურგჩანთის დპ 2ⁿ ქვესიმრავლის ცდას ცვლის ერთი „ავიღოთ თუ არა“ გადაწყვეტილებით თითო უჯრაში.

გზას უხსნის→

12P და NP, ალგორითმის არჩევა0-1 ზურგჩანთა NP-რთულია; მისი O(n·W) ცხრილი სწრაფია მხოლოდ მანამ, სანამ W პატარაა.

1ისწავლე 2უყურე 3ითამაშე 4შეამოწმე 5ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01ამოცანის დასმა, ვარიანტები და ხარბის შეცდომა

მოცემულია N საგანი; i-ურ საგანს აქვს wᵢ > 0 წონა და pᵢ > 0 ღირებულება. უნდა ავარჩიოთ ქვესიმრავლე, რომლის ჯამური წონა არ აღემატება ზურგჩანთის W ტევადობას, ხოლო ჯამური ღირებულება მაქსიმალურია. ზოგადად ეს ამოცანა NP-სრულია, თუმცა ზომიერი W-სთვის მას დინამიური პროგრამირება ხსნის.

ლექციაში ჩამოთვლილია ვარიანტები: უწყვეტი (შეიძლება საგნის ნებისმიერი ნაწილის აღება), 0-1 (თითო საგნის ერთი ეგზემპლარი), შეზღუდული (არაუმეტეს kᵢ ეგზემპლარი), შეუზღუდავი (ნებისმიერი რაოდენობა), მულტიამორჩევით (თითო ჯგუფიდან ერთი) და მრავლობითი ზურგჩანთა.

ლექციის მაგალითი: W = 50, საგნები 10, 20, 30 კგ, ღირებულებით $60, $100, $120. უწყვეტ ამოცანაში ხარბი, წონის ერთეულის ღირებულებით, ოპტიმალურია: $240. 0-1 ამოცანაში ხარბი პირველ ორს იღებს ($160) და მესამე აღარ ეტევა, მაშინ როცა მე-2 და მე-3 საგნები $220-ს იძლევა. საგნის აღების აზრი იმაზეა დამოკიდებული, კიდევ რა ეტევა, ამიტომ დპ გვჭირდება.

02ჯერ ღირებულებების გარეშე: რომელი წონებია მიღწევადი?

ლექციის მიხედვით დავიწყოთ უფრო მარტივი ვარიანტით. საგანთა წონები შევინახოთ M მასივში და განვსაზღვროთ

T(i, j) = 1, თუ პირველი i საგნიდან რომელიმე ქვესიმრავლის წონა ზუსტად j-ია, და 0 წინააღმდეგ შემთხვევაში.

საწყისი მნიშვნელობები: T(0, 0) = 1 (არაფერს ვირჩევთ) და T(0, j) = 0, როცა j ≥ 1. რეკურენტული დამოკიდებულებები i, j ≥ 1-ისთვის:

T(i, j) = T(i−1, j), როცა j < M[i];
T(i, j) = max(T(i−1, j), T(i−1, j−M[i])), როცა j ≥ M[i].

სიტყვებით: j წონა i საგნით მიიღწევა, თუ ის i-ური საგნის გარეშეც მიიღწეოდა (არ ვიღებთ), ან თუ j − M[i] მიიღწეოდა და i-ური საგანი მას ავსებს (ვიღებთ).

მაგალითი: W = 16, M = 4, 5, 2, 7, 5. პირველ სტრიქონში 1-იანები 0-სა და 4-ზეა. მეორე საგნისთვის (M[2] = 5) პირველი სტრიქონის ყოველი 1-იანი ქვემოთ გადმოდის და +5-ითაც ინაცვლებს: ვიღებთ 0, 4, 5, 9. ანუ: არცერთი საგანი, პირველი, მეორე ან ორივე.

03სრული ცხრილი და პასუხის აღდგენა

იგივე გავიმეოროთ ხუთივე საგნისთვის. ბოლო სტრიქონში ყველა წონა 0-დან 16-მდე მიიღწევა, გარდა 1, 3, 8 და 15-ისა (სლაიდზე მხოლოდ 3, 8 და 15 წერია; 1 იქ გამორჩენილია). ყველაზე მძიმე ტვირთი, რომელიც ეტევა, ბოლო სტრიქონის მარჯვნიდან პირველი 1-იანია: 16.

იმის გასაგებად, რომელი საგნები იძლევა ამას, ლექცია ამ უჯრიდან უკან მიდის:

თუ ზემოთ 1-იანი წერია, წონა ამ საგნის გარეშეც მიიღწეოდა, ამიტომ გადავდივართ ზედა სტრიქონის იმავე სვეტში;
თუ ზემოთ 0 წერია, ეს საგანი აუცილებლად აღებულია: გადავდივართ წინა სტრიქონში იმ სვეტში, რომლის ინდექსი მიმდინარე სვეტისა და საგნის წონის სხვაობის ტოლია.

(5, 16)-დან: ზემოთ 1-ია, ავდივართ. (4, 16)-ში ზემოთ 0-ია, ესე იგი მე-4 საგანი (წონა 7) აღებულია, გადავდივართ (3, 9)-ზე. ზემოთ 1-ია, ავდივართ (2, 9)-ზე. ზემოთ 0-ია: მე-2 საგანი (წონა 5) აღებულია, გადავდივართ (1, 4)-ზე. ზემოთ 0-ია: პირველი საგანი (წონა 4) აღებულია და ვაღწევთ (0, 0)-ს. პასუხი: საგნები 1, 2, 4, ანუ 4 + 5 + 7 = 16.

იისფერი: უკან სვლა (5, 16)-დან. წითელი: წონები, რომლებსაც ვერცერთი ქვესიმრავლე ვერ იძლევა.

04ღირებულებები: ფსევდოპოლინომიალური O(n·W)

ღირებულებების შემთხვევაში მეთოდი იგივეა, უბრალოდ 1-იანების ნაცვლად ცხრილში ღირებულებათა ჯამები ჩაიწერება. K[i][w] = საუკეთესო ღირებულება პირველი i საგნით, თუ ჯამური წონა არ აღემატება w-ს:

K[i][w] = max(K[i−1][w], K[i−1][w−wᵢ] + pᵢ)

(მეორე ვარიანტი მხოლოდ მაშინ, როცა wᵢ ≤ w). პასუხია K[n][W], უკან სვლა კი ისევე მუშაობს: თუ K[i][w] ზედა უჯრის ტოლია, i-ური საგანი არ აღებულა. ლექციის სამ საგანზე, რომელთა წონები და ტევადობა 10-ჯერ შევამცირეთ (წონები 1, 2, 3, ტევადობა 5), კუთხეში 220 გამოდის.

სირთულეა O(n·W). ალგორითმებს, რომელთა სირთულეც ორი ცვლადის პოლინომისაგან წარმოდგება, ფსევდოპოლინომიალურს უწოდებენ: ისინი პოლინომიალურია W *რიცხვის* მიმართ, მაგრამ ექსპონენციალურია W-ს ჩასაწერი ბიტების მიმართ. პრაქტიკაში სწრაფად მუშაობენ, თუ რიცხვითი პარამეტრი ძალიან დიდი არ არის, და უიმედოა W = 10¹⁸-ზე. ამიტომაა ზურგჩანთა მაინც NP-სრული.

05ერთი მასივი: 0-1, შეუზღუდავი და შეზღუდული

i-ური სტრიქონი მხოლოდ i−1-ე სტრიქონს კითხულობს, ამიტომ ცხრილი ერთი dp[w] მასივით შეიძლება შეიცვალოს. ამის შემდეგ ციკლის მიმართულება წყვეტს, რომელ ვარიანტს ვხსნით:

0-1: ყოველი საგნისთვის w-ზე ციკლი W-დან wᵢ-მდე კლებით: dp[w] = max(dp[w], dp[w−wᵢ] + pᵢ). კლებით სვლისას dp[w−wᵢ] ჯერ ისევ ამ საგნამდელ მნიშვნელობას ინახავს, ამიტომ ყოველი საგანი მაქსიმუმ ერთხელ აიღება.
შეუზღუდავი: ციკლი ზრდით (ლექციის ბოლო პროგრამა გარე ციკლს ტევადობებზე ატარებს, შიგას საგნებზე). ახლა dp[w−wᵢ] შეიძლება უკვე შეიცავდეს i-ურ საგანს, ამიტომ ის ისევ და ისევ აიღება.
შეზღუდული (არაუმეტეს kᵢ ეგზემპლარი): საგანი kᵢ ცალკე 0-1 საგნად განიხილე, ან დაყავი 1, 2, 4, … ზომის ნაწილებად, რომ მხოლოდ O(log kᵢ) საგანი დაემატოს.

მეხსიერება O(W)-მდე მცირდება. მიღწევადობის ვარიანტი ასევე მუშაობს ლოგიკური მნიშვნელობებით, ან wᵢ-ით წანაცვლებული bitset-ით, რაც ძალიან სწრაფია.

ლექციის C++ კოდიC++

მე-14 სლაიდი: K[i][w] არის საუკეთესო ღირებულება პირველი i საგნით და w ტევადობით, ყოველი უჯრა კი ან გამოტოვებს i-ურ საგანს, ან აიღებს მას და K[i-1][w-wt[i-1]]-ს დაუმატებს.

#include <bits/stdc++.h>
using namespace std;
int knapSack(int W, int wt[], int val[], int n){
    int i, w;
    int K[n+1][W+1];
    for (i=0; i<=n; i++) {
        for (w=0; w <= W; w++) {
            if (i==0 || w==0) K[i][w]=0;
            else if (wt[i-1] <= w)
                K[i][w]=max(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w]);
            else
                K[i][w]=K[i-1][w];
        }
    }
    return K[n][W];
}
int main(){
    int i, n, val[20], wt[20], W;
    cin>>n>>W;  //n-number of items, w-size of knapsack
    for(i = 0;i < n; ++i){
        cin>>val[i]>>wt[i]; //value and weight of items
    }
    cout<<knapSack(W, wt, val, n);
    return 0;
}

ფასი ერთი შეხედვით

მიღწევადობის ცხრილი T ან ღირებულებების ცხრილი KO(n·W)

მეხსიერება ერთი dp[w] მასივითO(W)

არჩეული საგნების აღდგენაO(n)

დაიმახსოვრე

0-1 ზურგჩანთაში ცხრილის i-ური სტრიქონი გვეუბნება, რა მიიღწევა პირველი i საგნით, და ყოველი უჯრა ან ზედა უჯრას იმეორებს (არ ვიღებთ), ან ზედა სტრიქონის იმ უჯრას კითხულობს, რომელიც wᵢ სვეტით მარცხნივაა (ვიღებთ).
პასუხიდან უკან სვლისას: თუ იგივე მნიშვნელობა ზემოთაც წერია, საგანი არ აღებულა, თორემ აღებულია და მის წონაზე მარცხნივ ვხტებით.
O(n·W) ფსევდოპოლინომიალურია: კარგია ზომიერი ტევადობისთვის, უსარგებლოა უზარმაზარისთვის, და ამიტომაა ზურგჩანთა მაინც NP-სრული.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: ეს ლექციის ცხრილია: უყურე, როგორ იმეორებს ყოველი სტრიქონი ზედა 1-იანებს და ამატებს ახლებს საგნის წონით წანაცვლებულს, შემდეგ კი მიჰყევი უკან სვლას მე-16 სვეტიდან. „სცადე შენით“-ში ღირებულებები დაამატე და K[i][w] ვერსიას ნახავ.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

მიღწევადობის ცხრილი (W = 16), წონები: 4, 5, 2, 7, 5

i\\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1 (w=4)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2 (w=5)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3 (w=2)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
4 (w=7)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
5 (w=5)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

არჩეული საგნები

(ჯერ არაფერია)

T[0][0] = 1: ნული საგნით მხოლოდ 0 წონის მიღებაა შესაძლებელი.

ფსევდოკოდი

 1 T[0][0] = 1   // weight 0 is always reachable 2 for i in 1..n:      // consider item i 3   for j in 0..W: 4     if T[i-1][j]==1: T[i][j]=1        // skip item i 5     if T[i-1][j]==1 and j+w[i]<=W: T[i][j+w[i]]=1  // take it 6 answer = rightmost 1 in row n 7 backtrack: T[i-1][j]==1 ? skip item i : take it, j -= w[i] 8 // with values p[i]: K[0][w] = 0 9 K[i][w] = max(K[i-1][w], K[i-1][w-w[i]] + p[i])  // skip or take10 answer K[n][W]; backtrack: K[i][w] != K[i-1][w] ⇒ item i taken

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

წონები 3 და 5, W = 10 (მიღწევადობის ვარიანტი). რომელი წონებია მიღწევადი ბოლო სტრიქონში?

№2

0-1 ზურგჩანთისთვის ერთ dp[w] მასივს იყენებ, მაგრამ w-ზე ციკლი ზრდით მიდის. რა ფუჭდება?

№3

n = 100 საგანი, W = 10⁹. კარგი იდეაა O(n·W) დპ?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodePartition Equal Subset Sum საშუალო↗CSESMoney Sums საშუალო↗CSESBook Shop საშუალო↗LeetCodeCoin Change II საშუალო↗CSESTwo Sets II მოწინავე↗