ზურგჩანთის უწყვეტი ამოცანა

ქურდს 50 კილოგრამიანი ჩანთა აქვს, წინ კი ოქროს ქვიშა, ვერცხლის ქვიშა და სანელებლები ხვდება. როცა ნებისმიერი რამის ნებისმიერი ნაწილის აღება შეიძლება, საუკეთესო გეგმა საოცრად მარტივია: ჯერ ყველაზე ძვირი კილოგრამი.

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

←ეყრდნობა

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

გზას უხსნის→

100-1 ზურგჩანთის ამოცანაროცა ნივთის გაყოფა არ შეიძლება, ხარბი შეფარდება ცდება და ცხრილი გვჭირდება.

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

ისწავლე

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

01ზურგჩანთის ამოცანა

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

ზოგადად ეს ამოცანა NP-სრულია: მისი ამოხსნის პოლინომიალური ალგორითმი ნაპოვნი არ არის. მცირე N-ებისთვის მას დინამიური პროგრამირება ხსნის, და ეს ლექციის მეორე ნახევარია (ეტაპი 10).

ჩვენი მაგალითი ლექციისაა: სამი საგანი, 10, 20 და 30 კგ, ღირებულებით $60, $100 და $120, ზურგჩანთის ტევადობა 50. სამივე ერთად 60 კგ-ია, ამიტომ რაღაც უნდა დარჩეს.

02ერთი ამოცანის ექვსი ვარიანტი

ლექცია ჯერ ვარიანტებს ჩამოთვლის, რადგან ის, თუ რამდენის აღება შეიძლება თითო საგნიდან, წყვეტს, რომელი ალგორითმი იმუშავებს:

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

ხარბ ალგორითმს მხოლოდ უწყვეტი ვარიანტი ემორჩილება. დანარჩენებს დინამიური პროგრამირება ან უფრო მძიმე მეთოდები სჭირდება.

03უწყვეტი ამოცანა: ჯერ ყველაზე ძვირი კილოგრამი

ვიპოვოთ თითოეული საგნის წონის ერთეულის ღირებულება: 60/10 = 6, 100/20 = 5, 120/30 = 4 დოლარი კილოგრამზე. რადგან ნებისმიერი ნაწილის აღება შეიძლება, კილოგრამი კილოგრამია, და ცხადია, ყველაზე ძვირი კილოგრამები გვინდა.

ამიტომ: პირველი საგანი მთლიანად ჩავდოთ (10 კგ, $60), მერე მეორეც მთლიანად (30 კგ, $160). მესამე აღარ ეტევა, ამიტომ ავიღოთ მისი ორი მესამედი: 20 კგ, $80. ზურგჩანთა ზუსტად სავსეა, ღირებულება $240.

რატომ არის ეს ოპტიმალური: თუ ამოხსნაში იაფი საგნის რომელიმე კილოგრამია, გარეთ კი უფრო ძვირი კილოგრამი დარჩა, მათი გაცვლა ღირებულებას გაზრდის. ე.ი. საუკეთესო ამოხსნა უკეთეს კილოგრამს გარეთ არასდროს ტოვებს, და სწორედ ამას აგებს ხარბი.

04აკრძალე დაყოფა და ხარბი ტყდება

იგივე საგნები, ოღონდ ახლა 0-1 წესით: ნაწილების აღება არ შეიძლება. ხარბი „ჯერ საუკეთესო $/კგ“ ჩადებს პირველ საგანს (კილოგრამზე ყველაზე ძვირფასია), მერე მეორეს, მესამე კი აღარ ეტევა. შედეგი: $160.

მაგრამ მეორე და მესამე საგნები ერთად ზუსტად 50 კგ-ია და $220 ღირს. ხარბმა წააგო, რადგან საგნებს სიმკვრივით აფასებდა, დარჩენილი ადგილი (20 კგ) კი მთლიანი საგნით ვეღარ შეივსო.

უწყვეტ ამოცანაში დარჩენილი ადგილი არასდროს იკარგება, ამიტომაა იქ იგივე წესი ოპტიმალური. ნაწილების გარეშე კომბინაციების შედარება გვიწევს, და ეს უკვე 0-1 ზურგჩანთის ცხრილის საქმეა მე-10 ეტაპზე.

ყოველი ზოლი 50 კგ-იანი ზურგჩანთაა; ბოლო სტრიქონი უწყვეტი ამოცანის პასუხია.

05ალგორითმი და ლექციის კოდი

ლექციიდან: საგნები დავალაგოთ მასის ერთეულის ღირებულების (ღირებულება გაყოფილი წონაზე) არაზრდადობით და თანმიმდევრულად ავიღოთ, ვიდრე ზურგჩანთა არ შეივსება. შესაძლოა, ბოლო საგნიდან მხოლოდ ნაწილის აღება მოგვიწიოს. თუ საგნების ჯამური წონა W-ზე ნაკლები არ არის, ზურგჩანთა ყოველთვის ბოლომდე შეივსება.

ლექციის C++ კოდი თითო საგანს ინახავს როგორც pair<double,double> (ღირებულება, წონა), ალაგებს კომპარატორით a.first/a.second > b.first/b.second, შემდეგ კი ციკლში:

თუ items[i].second <= capacity: ვიღებთ მთლიანად, capacity -= weight, mx += value;
სხვა შემთხვევაში: mx += value / weight * capacity, capacity = 0 და ვჩერდებით.

სორტირება O(n log n)-ია, ციკლი O(n). გამოიყენე double (ან ზუსტი წილადები), რადგან პასუხი შეიძლება მთელი არ იყოს.

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

მე-6 სლაიდი: comp_item საგნებს წონის ერთეულის ღირებულებით ალაგებს (first ღირებულებაა, second კი წონა), შემდეგ ციკლი მთლიან საგნებს იღებს, ვიდრე ბოლო საგანი მხოლოდ ნაწილობრივ არ ჩაეტევა.

#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> item;
bool comp_item(item& a, item& b){
    return a.first/a.second > b.first/b.second;
}
double mx_profit(item items[], int n, double capacity){
    double mx= 0;
    sort(items, items+n, comp_item);
    for(int i= 0; i<n; i++){
        if(items[i].second <= capacity){
            capacity -= items[i].second; mx+= items[i].first;
        }
        else{
            mx+= items[i].first/items[i].second * capacity;
            capacity= 0; break;
        }
    }
    return mx;
}
int main( ) {
    int n;   item items[100];  double capacity;
    cin>>n>>capacity;
    for(int i=0; i<n; i++){
        cin>>items[i].first>>items[i].second;
    }
    cout<< mx_profit(items, n, capacity) <<endl;
}

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

დალაგება ღირებულება/წონითO(n log n)

ხარბი შევსებაO(n)

დამატებითი მეხსიერებაO(1)

დაიმახსოვრე

უწყვეტი ზურგჩანთა: დაალაგე კილოგრამის ღირებულებით და ხარბად შეავსე; მხოლოდ ბოლო საგანი იყოფა.
ეს ოპტიმალურია, რადგან შიგნით იაფი და გარეთ ძვირი კილოგრამის გაცვლა ყოველთვის მოგებიანი იქნებოდა.
0-1 ვარიანტში იგივე წესი ცდება ($160 და $220), ამიტომ იქ დინამიური პროგრამირებაა საჭირო.

უყურე

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

▶

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

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

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

ითამაშე

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

👀 რას უყურო: უყურე თითო საგნის $/კგ-ს: ზურგჩანთა სწორედ ამ რიგით ივსება და მხოლოდ ბოლო საგანი იქცევა პროცენტად.

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

ზურგჩანთის უწყვეტი ამოცანა (ხარბი)

#1 · 10კგ / $60
6.0 $/კგ#2 · 20კგ / $100
5.0 $/კგ#3 · 30კგ / $120
4.0 $/კგ

ტევადობა 50კგ · ჯამური ღირებულება: $0

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

ფსევდოკოდი

 1 each item has weight w and value p 2 sort items by value/weight ratio, descending 3 take whole items greedily while they fit 4 the last item may be taken as a FRACTION to fill exactly 5 // optimal because items are divisible

1 / 1

შეამოწმე

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

№1

საგნები (წონა, ღირებულება): A (5, $50), B (10, $60), C (20, $140). ტევადობა 20, ნაწილები დაშვებულია. მაქსიმალური ღირებულება?

№2

რატომ ცდება „ჯერ საუკეთესო $/კგ“ 0-1 ზურგჩანთაში?

№3

თითო საგნის აღება ნებისმიერი რაოდენობით შეიძლება (მხოლოდ მთლიანი ეგზემპლარები). რომელი ვარიანტია?

ივარჯიშე

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

LeetCodeMaximum Units on a Truck დამწყები↗LeetCodeMaximum Bags With Full Capacity of Rocks საშუალო↗LeetCodeMaximum Price to Fill a Bag საშუალო↗CSESBook Shop (0-1 knapsack, needs DP) საშუალო↗