NP çantası problemi
Klassik NP-tam məsələlərdən biri olan Çanta Problemi aşağıdakı kimi təsvir edilir.
n sayda əşya verilir, hər biri kütlə w[i] və faydalılıq p[i] ilə xarakterizə olunur. Məqsəd bu əşyaların elə bir dəstini seçməkdir ki, bu dəstin ümumi kütləsi w-dən çox olmasın və ümumi faydalılığı maksimum olsun.
Giriş Məlumatları
Birinci sətir təbii ədədlər n (1 ≤ n ≤ 20) və w (1 ≤ w ≤ 10^9) ehtiva edir. Sonra n sətir gəlir, hər birində iki ədəd: w[i] - i-ci əşyanın kütləsi və onun faydalılığı p[i] (1 ≤ w[i], p[i] ≤ 10^9).
Çıxış Məlumatları
Birinci sətirdə seçilmiş əşyaların sayını və onların ümumi faydalılığını göstərin. Növbəti sətirdə onların nömrələrini artan sırada göstərin (əşya nömrələri girişdə verildiyi sıraya uyğun olaraq birdən başlayır).
Əgər bir neçə dəst tapılarsa, ən az əşya olan dəsti seçin. Əgər bu halda da cavab qeyri-müəyyəndirsə, birinci əşyanın mümkün olan ən kiçik nömrəyə malik olduğu dəsti seçin, bu cür variantlardan ikinci əşyanın mümkün olan ən kiçik nömrəyə malik olduğu dəsti seçin və s.