Теория

1. Даны W, N, a₁, a₂, ..., a_N. a_i --- вес i-го предмета. Каждый предмет можно или брать, или не брать.
2. Тоже самое, но теперь памяти нужно использовать O(W).
3. А теперь нужно набрать не ровно W, а максимальную величину <= W.
4. А теперь у каждой вещи есть 2 характеристики --- a_i, c_i.
5. В задачах 1-4 научиться восстанавливать ответ (множество, которое мы берем).
6. А теперь решить задачи 1-5 с условием, что каждую вещь можно брать сколько угодно раз.
7. А теперь решить задачи 1-5 с условием, что каждую вещь можно брать K_i раз.
8. Посчитать количество способов получить вес W за O(NW).

Практика

1. timus : 1005
2. timus : 1017
3. timus : 1182
4. timus : 1244
5. 101018_30 : A (Про золотой песок)
6. 101018_30 : B (Nearest Approximation)

Задачи про слагаемые (теория)

1. Сколько способов число N представить в виде суммы возрастающих слагаемых, каждое слагаемое не более K?
2. Сколько способов число N представить в виде суммы ровно K возрастающих слагаемых?
3. Сколько способов число N представить в виде суммы ровно K слагаемых?