Türkçe Bilgi logo TürkçeBilgi

Knapsack Problemi

Kısaca: Sırt çantası problemi (İngilizce: "knapsack problem") bir klasik yöneylem araştırması ve matematiksel olarak "kombinatorik optimizasyon" problemidir. ...devamı ☟

Knapsack problemi
Knapsack Problemi

düzenle|Ağustos 2007 Knapsack(sırt çantası) problemi en ünlü NP-Hard problemleri arasındadır. Pseudo-polynomial zamanda çözümünü sağlayan algoritmalar bulunmaktadır. Problemin karar problemi versiyonunun NP-Complete olduğu kanıtlanmıştır. Problemin polynomial zamanda çözümü ispatlanabilirse P=NP de ispatlanmış olacaktır.

Problem tek kısıtlı bir maksimizasyon problemlemidir. Değişkenler sadece "0" veya "1" değerlerini alabilirler. Formülasyonu şu şekildedir:

maximize \sum_^n p_j x_j.
Şu kısıtlara bağlı olarak \sum_^n w_j x_j \le c, \quad \quad x_j = 0\;\mbox\;1, \quad j=1,\dots,n.




Kaynaklar

Vikipedi

Bu konuda henüz görüş yok.
Görüş/mesaj gerekli.
Markdown kullanılabilir.

Knapsack problemi Resimleri