Knapsack problem – Sırt çantası problemi

Knapsack problemi, basitçe sırt çantası problemi veya torba problemi olarak adlandırılabilir. Bu problemde, bir torbanın istenen durumlara göre maksimum verim alabileceği şekilde içerisine eşyaların yerleştirilmesi konu edinilir.

Örneğin maksimum kazanç veya maksimum sayıda eşyanın bir torbanın içerisine yerleştirilmesi istenir. Bu örnekte torbanın ağırlığına göre maksimum kazanç ile toplamda 10x değerinde 3 eşya yerleştirilebilirken, maksimum eşya durumunun gerçekleşmesini istediğimizde 5x değerinde 5 eşya yerleştirebildiğimizi varsayalım.

Bu durumda eğer daha değerli eşyaları taşımak istersek, torba içerisine yalnızca 3 eşya alabiliriz fakat daha fazla eşyayı torba içerisine koymak istersek, 5 eşya alabiliriz. Her durumda, belirttiğimiz koşula uygun olarak maksimum kazancı elde etmiş sayılırız.

Herhangi bir olayda maksimum verim elde etme amacıyla knapsack solution uygulanabilir. Bu çözüm uygulanırken, aç gözlü veya brute force yaklaşım izlenebilir.

Bu yaklaşımı basitçe Java programlama diliyle yazdım ve Github hesabıma ekledim. Kodların linkine ulaşmak için tıklayınız.