|
| Задача #1. Рюкзак - 1 |
| Имя входного файла |
input.txt |
| Имя выходного файла |
output.txt |
| Максимальное время работы на одном тесте |
2 секунды |
|
|
Имеется N неделимых
предметов. Для каждого предмета известна его стоимость (в
рублях) и масса (в кг.). Величины стоимости и массы являются
натуральными числами. Ваша цель состоит в том, чтобы
определить, существует ли набор, суммарная масса предметов
которого ровно K кг. Если такой набор
существует, то требуется определить такой список предметов в
наборе, чтобы их суммарная стоимость была максимальной. При
этом каждый предмет может входить в набор только один раз.
Формат входных данных
В первой строке входного файла находятся два
числа N и K (1<=N,K<=100). Далее идет N пар натуральных чисел m[i] -- масса i-ого
предмета и c[i] -- стоимость i-го предмета (1<=m[i],c[i]<=100).
Формат выходных данных
Если искомого набора не существует, выходной
файл должен содержать одно число -1, иначе файл должен
соджержать максимальную стоимость и предметы, входящие в
соответствующий набор.
| Пример входного файла |
Пример выходного файла |
5 16
4 5 5 7 3 4 7 9 6 8 |
21
1 2 4 | |
| Задача #2. Рюкзак - 2 |
| Имя входного файла |
input.txt |
| Имя выходного файла |
output.txt |
| Максимальное время работы на одном тесте |
2 секунды |
|
|
Дан массив чисел А[1..N], элементы которого являются
натуральными числами. Определить, можно ли заданное число K разложить на слагаемые таким образом,
чтобы в качестве слагаемых использовались только числа из
массива А, при этом каждое число не
более 1-го раза.
Формат входных данных
В первой строке входного файла содержатся два
числа N и K (1<=N,K<=1000). Далее идет N натуралдьных чисел A[i] (1<=A[i]<=100).
Формат выходных данных
Если такой набор существует, в выходной файл
необходимо вывести YES, иначе вывести NO.
| Пример входного файла |
Пример выходного файла |
4 10
4 3 1 5 |
YES | |
| Задача #3. Рюкзак - 3 |
| Имя входного файла |
input.txt |
| Имя выходного файла |
output.txt |
| Максимальное время работы на одном тесте |
2 секунды |
|
|
Дан массив чисел А[1..N], элементы которого являются
натуральными числами. Определить, можно ли заданное число K разложить на слагаемые таким образом,
чтобы в качестве слагаемых использовались только числа из
массива А, каждое число использовалось
не более одного раза и при этом число слагаемых должно быть
минимаьлно.
Формат входных данных
В первой строке входного фала содержатся два
числа N и K (1<=N,K<=1000). Далее идут N натуральных чисел A[i] (1<=A[i]<=100).
Формат выходных данных
Если такой набор существует, в выходной файл
необходимо вывести YES и одно число -- количество слагаемых,
иначе вывести NO.
| Пример входного файла |
Пример выходного файла |
4 6
4 3 1 2 |
YES 2 | |
Назад
|
