![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/langka-640px-Knapsack.svg.png&w=640&q=50)
ზურგჩანთის ამოცანა
From Wikipedia, the free encyclopedia
ზურგჩანთის ამოცანა — ამოცანა კომბინატორულ ოპტიმიზაციაში. პირობა შემდეგია, მოცემულია ნივთები, თითოეულს აქვს წონა და გარკვეული ღირებულება. უნდა გავარკვიოთ, თუ რა რაოდენობის ნივთი უნდა ავარჩიოთ, რომ მთლიანი წონა არაუმეტესი იყოს მოცემულ x-წონაზე, და აგრეთვე რაც შეიძლება დიდი იყოს ნივთების საერთო ღირებულება. გარკვეულწილად ეს ამოცანა ცხოვრებისეულია, როდესაც ჩანთის ზომა შეზღუდულია, ვცდილობთ რაც შეიძლება ღირებული და მნიშვნელოვანი ნივთები ავარჩიოთ.
ამ სტატიაში არ არის მითითებული სანდო და გადამოწმებადი წყარო. |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/Knapsack.svg/320px-Knapsack.svg.png)
ზურგჩანთის ამოცანა საკმაოდ ძველია, მე-19 საუკუნიდან ერთ საუკუნეზე მეტი ის შესწავლის საგანი იყო. „ზურგჩანთის ამოცანის“ სახელი უკავშირდება ამერიკელ მათემატიკოსს ტობიას დანციგს.