Стандартное решение задачи о рюкзаке — O(nW), где мы будем увеличивать вес на +1 за раз, чтобы добраться до решения.
Есть ли какой-нибудь подход к проблеме рюкзака, который не требует увеличения веса на +1 за раз.
например Один из способов, который я могу придумать, - это разделить все числа на их общий знаменатель.
Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]
