Масъалаи ҷузвдон

Масъалаи ҷузвдон

Муқаддима

Масъалаи ҷузвдон — ин масъалаи оптимизатсионӣ аст, ки дар он бояд муайян кард, кадом ашёҳоро ба ҷузвдони (ранец) дорои ғунҷоиши маҳдуд гузоштан лозим, то ки арзиши умумӣ ҳадди аксар гардад. Ашёҳо метавонанд ҳам бутун ва ҳам касрӣ бошанд. Дар ин боб мо танҳо варианти бутун-ро (0/1 knapsack) баррасӣ мекунем, зеро варианти касрӣ бо усули ҳарисона ҳал мешавад.

Гузориш:
Дода шудааст $N$ ашё, ҳар кадом вазн ва арзиш дорад, ва ҷузвдоне бо ғунҷоиши $W$ ($W > 0$). Бояд баъзе ашёҳоро интихоб кард, то ки вазни умумии онҳо аз $W$ зиёд нашавад, ва арзиши умумӣ ҳадди аксар бошад. Ашёҳоро ба қисмҳо ҷудо кардан мумкин нест.

Мисол: ҳангоми $W = 5$, ва ашёҳо , , (рақами аввал — арзиш, рақами дуюм — вазн) метавон арзиши максималии -ро ба даст овард, агар ба ҷузвдон ва -ро гузорем (вазн ).