Knapsack problemi

Vikipedi, özgür ansiklopedi

Git ve: kullan, ara
Düzenle Bu madde ya da bir kısmı, Vikipedi standartlarına uygun değildir ve bu nedenle düzenlenmesi gerekmektedir.
Maddeyi Vikipedi standartlarına uygun biçimde düzenleyip, geliştirerek Vikipedi'ye katkıda bulunabilirsiniz. NOT:Gerekli değişiklik yapılmadan bu şablon kaldırılmamalıdır.
Bu madde Ağustos 2007 tarihinden beri, düzenleme isteğiyle etiketlidir.

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_{j=1}^n p_j x_j.
Şu kısıtlara bağlı olarak \sum_{j=1}^n w_j x_j \le c, \quad \quad x_j = 0\;\mbox{or}\;1, \quad j=1,\dots,n.

"http://tr.wikipedia.org/wiki/Knapsack_problemi" adresinden alındı.