ზურგჩანთის ამოცანა: განსხვავება გადახედვებს შორის

მასალა ვიკიპედიიდან — თავისუფალი ენციკლოპედია
[შეუმოწმებელი ვერსია][შეუმოწმებელი ვერსია]
შიგთავსი ამოიშალა შიგთავსი დაემატა
ხაზი 6: ხაზი 6:


== ამოხსნა ==
== ამოხსნა ==
ამ ამოცანის რამდენიმე ინტერპრეტაცია არსებობს. 0/1 ზურგჩანთის ამოცანა: გულისხმობს, რომ ნივთი ან უნდა ავიღოთ, ან არა. ეს ამოცანა დინამიური პროგრამირების საშუალებით იხსნება, საჭიროა ოპტიმიზირებული სრული გადარჩევის შემუშავება.
ამ ამოცანის რამდენიმე ინტერპრეტაცია არსებობს. 0/1 ზურგჩანთის ამოცანა გულისხმობს, რომ ნივთი ან უნდა ავიღოთ, ან არა. ეს ამოცანა დინამიური პროგრამირების საშუალებით იხსნება, საჭიროა ოპტიმიზირებული სრული გადარჩევის შემუშავება.


'''იმპლემენტაცია C++-ზე:'''
'''იმპლემენტაცია C++-ზე:'''

19:53, 13 მარტი 2020-ის ვერსია

ზურგჩანთის ამოცანა. ზურგჩანთის მაქსიმუმი: 15 კგ. 4 ნივთი, თითოეულს როგორც წონა, ასევე ღირებულება გააჩნია.

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

ზურგჩანთის ამოცანა საკმაოდ ძველია, მე-19 საუკუნიდან ერთ საუკუნეზე მეტი ის შესწავლის საგანი იყო. "ზურგჩანთის ამოცანის" სახელი უკავშირდება ამერიკელ მათემატიკოსს ტობიას დანციგს.

ამოხსნა

ამ ამოცანის რამდენიმე ინტერპრეტაცია არსებობს. 0/1 ზურგჩანთის ამოცანა გულისხმობს, რომ ნივთი ან უნდა ავიღოთ, ან არა. ეს ამოცანა დინამიური პროგრამირების საშუალებით იხსნება, საჭიროა ოპტიმიზირებული სრული გადარჩევის შემუშავება.

იმპლემენტაცია C++-ზე:

#include <iostream>

using namespace::std;

long long weight[100], value[100], dp[100005];
int main() {
    // ნივთების რაოდენობა - n
    // წონის ლიმიტი  - w
    int n, w; 
    cin >> n >> w;
    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = w; j >= weight[i]; j--){
            // თითოეული წონისთვის უნდა გამოვთვალოთ მაქსიმალური ჯამური
            // ღირებულება.  როგორც ვახსენეთ, ნივთი ან უნდა ავიღოთ, ან არა.
            // რადგან უდიდესი  ღირებულება გვჭირდება, უნდა გავაკეთოთ ყველაზე
            // მომგებიანი არჩევანი.
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    
    cout << dp[w];
    return 0;
}