И да, решить надо методом динамического программирования

>>5529
>Нужно определить минимальную вместимость ранца с суммарной ценностью большей либо равной заданному значению

42.
и для второго варианта ... 42.

Это не "обратная", а просто задача о ранце, только с чуть измененной формулировкой. Решения (методом динамического программирования, ага) есть в вики. Их нужно только чуть доработать напильником.

Например, для случая, когда можно брать несколько предметов, делаем так:
Пусть w[n] - минимальный вес ранца, стоимость которого составляет n денег. w[0] = 0. Для того, чтобы найти очередной (когда все w[0],...,w[n-1] уже найдены) w[n], рассматриваем все предметы стоимостью x <= n, вычисляем, сколько будет весить ранец, если к w[n-x] прибавить вес этого предмета, из всех полученных варинатов выбираем наименьший, записываем полученное значение в w[n]. Если предметов стоимостью меньше n не найдется, записываем в w[n] минус бесконечность.
Когда мы вычислим w[N], где N - требуемая стоимость, у нас будет два варианта - либо w[N] > 0, тогда это и есть решение, либо там будет минус бесконечность - тогда надо продолжать вычислять последующие w[n] до получения первого положительного числа.

>>5539
> минус бесконечность
Логичнее заменить на плюс бесконечность.
> Когда мы вычислим w[N], где N - требуемая стоимость, у нас будет два варианта - либо w[N] > 0, тогда это и есть решение, либо там будет минус бесконечность - тогда надо продолжать вычислять последующие w[n] до получения первого положительного числа.
Так не пойдёт, ибо w[n] не обязательно монотонно неубывает по n. Тут надо либо считать элементы массива вплоть до N + wmax - 1 (где wmax - максимальный вес предмета) и брать за результат min(w[N], ..., w[N + wmax - 1]), либо обозначать за w[n] минимальный вес ранца, стоимость которого не меньше n денег (при этом все неположительные элементы массива равны нулю, и хранить их не обязательно; перебирать надо каждый раз все предметы, а доказательство корректности решения слегка нетривиально).
Ах да, я надеюсь на то, что все веса положительны, иначе здравый смысл летит к чертям.

>>5546
Да, я херню написал.
> надо либо считать элементы массива вплоть до N + wmax - 1
N - рубли, wmax - килограммы. Тут что-то не так...
> либо обозначать за w[n] минимальный вес ранца, стоимость которого не меньше n денег
Вот это похоже на правду, но доказательство корректности действительно какое-то неочевидное.

А вот второй вариант задачи (когда предмет либо кладеся, либо нет), кажется, решается совсем просто.
Заводим массив w[Nmax], где Nmax - суммарная стоимость всех предметов. w[0] = 0, остальные - плюс бесконечность.
Дальше для каждого предмета идем по всему массиву (до тех пор, пока i + стоимость предмета не станет больше Nmax) и если w[i + стоимость этого предмета] больше, чем w[i] + вес этого предмета, заменяем первое на второе. Всего это потребует O(количество предметов, умноженное на их максимальную стоимость) операций. После этого выбираем наименьшее из w[N]...w{Nmax].

О, у меня появилась идея, как это адаптировать для первого варианта.
Инициализуем массив w[Nmax] точно так же. Далее точно так же по очереди рассматриваем каждый j-ый предмет (весом W[j] и стоимостью P[j]).
Точно так же проходим по всему массиву for (i = 0; i + P[j] < Nmax; i++), и если w[i + P[j]] > w[i] + W[j] то w[i + P[j]] = w[i] + W[j]. А вот потом проходим по нему еще раз, только вместо P[j] и W[j] прибавляем 2P[j] и 2W[j]. А потом - 3P[j] и 3W[j], и так далее до тех пор пока kP[j] не станет больше Nmax.
Сложность, правда, получится кубическая.

>>5547
> N - рубли, wmax - килограммы. Тут что-то не так...
Действительно, не так. Не максимальный вес там нужен, а максимальная цена, pmax.
> доказательство корректности действительно какое-то неочевидное
Сейчас понял, что пройдёт самое обыкновенное для динамического программирования индуктивное доказательство, если за базу индукции взять утверждение "w[n] = 0 при n <= 0".

> Дальше для каждого предмета идем по всему массиву (до тех пор, пока i + стоимость предмета не станет больше Nmax)
Поправка: тут надо идти от конца массива к началу, чтобы случайно не использовать значения, найденные на текущей итерации (и тем самым не положить один предмет дважды). Трюк с определением w[n] как наименьшего веса набора цены, не меньшей n, в этом варианте, кажется, тоже сработает.