Решение задачи О рюкзаке методом динамического программирования
Имеется рюкзак с заданной вместимостью (под вместимостью понимается максимально возможная масса), и имеются предметы (n штук), причем каждый предмет характеризуется массой w и ценностью P.
w = {w1, w2, …, wn}
p={p1, p2, …, pn} Требуется собрать рюкзак с максимальной ценностью и минимальным возможным весом, не превышающим Wmax.
1 способ: перебор (простой)
2 способ: метод ветвей и границ, который заключается в умном переборе. Могут быть случаи, когда перебираются все возможные варианты.
3 способ: использование «жадного» алгоритма (берется каждый текущий момент («лучший» элемент), ориентированный на их относительной точности). Решение будет получено достаточно быстро, но не факт, что оно будет оптимальным. Математическая формулировка задачи Имеется рюкзак с целочисленным значением «весова» W. Имеется n предметов, характеризующихся целочисленными показателями весов wi и ценностей pi. Требуется построить вектор бинарных величин В = {b1, b2, …, bn} (0 – не положили в рюкзак, 1– положили) так, чтобы при выполнении ограничения b1w1 + b2w2 + … + bnwn = ( )=