Проблем с алгоритъма на раницата, решение - програмиране на C, C # и Java

Уроци по програмиране, алгоритми, статии, изходни кодове, програмни примери и полезни съвети

Проблем с раницата: алгоритъм, решение

Проблемът с раницата е един от най-популярните проблеми на комбинаторната оптимизация. В тази статия ще разгледаме формулирането му и ще изпълним решението, като използваме един от методите, използващи езика за програмиране C #.

Формулиране на проблема с раницата

Ето класическата формулировка проблеми с раницата (проблеми с раницата).

Състояние: Има раница с ограничен капацитет за тегло; има и набор от неща с определено тегло и стойност. Необходимо е да изберете такъв набор от неща, така че да се побира в раница и да има максимална стойност (цена).

решение

Алгоритъм за решаване на проблема с раницата

Помислете за един от най-простите начини точно решение проблеми с раници: това е начинът груба сила.

Нека обозначим максималното тегло на раницата като W и броя на различните неща N. В този случай комплектът може да съдържа абсолютно еднакви предмети.