Найдите максимальный вес золота, который можно унести в
рюкзаке вместительностью s, если имеются n золотых слитков с заданными весами.
Вход. Первая строка содержит одно целое число s (1 ≤ s ≤ 104) – вместительность рюкзака. Далее следуют n (1 ≤ n ≤ 300) неотрицательных целых чисел, не превосходящих 105 – веса слитков.
Выход. Выведите максимальный вес
золота, который можно унести в рюкзаке.
Пример
входа |
Пример
выхода |
20 5 7 12 18 |
19 |
динамическое
программирование
Анализ алгоритма
Заведем массив
m, в котором m[i] установим в 1, если
можно набрать вес в точности i
имеющимися слитками. Изначально положим m[0] = 1.
Пусть массив m
уже заполнен требуемым образом для некоторого множества слитков. Приходит
следующий слиток веса w. Тогда
следует положить равным 1 все такие m[i]
(w ≤ i ≤ s), для которых
m[i – w] = 1.
Ответом будет наибольший вес, не больший s, который
можно унести в рюкзаке.
Пример
Для заданного примера максимальный вес 19 достигается для
подмножества {7, 12}.
Заполнение ячеек
массива m с приходом очередного слитка. Слева указаны массы слитков.
Реализация алгоритма
Объявим рабочий массив.
#define MAX 10010
int m[MAX];
Читаем входные
данные.
scanf("%d",&s);
Инициализация массива m.
memset(m,0,sizeof(m));
m[0] = 1;
Обрабатываем
очередной слиток весом w. Проходим по
массиву m справа налево и устанавливаем в 1 все такие m[i] (w ≤ i ≤ s), для которых m[i – w] = 1.
while(scanf("%d",&w)
== 1)
{
for(i = s; i >= w; i--)
if (m[i - w] == 1) m[i] = 1;
}
Ищем наибольший вес, не больший s, который можно унести в рюкзаке, и
выводим его.
for(i = s;; i--)
if (m[i] > 0) break;
printf("%d\n",i);
Реализация
алгоритма – bitset
#include <cstdio>
#include <cstring>
#include <bitset>
#define MAX 10010
using namespace std;
bitset<MAX> m;
int i, s, w;
int main(void)
{
scanf("%d",
&s);
m[0] = 1;
while
(scanf("%d", &w) == 1)
{
for (i =
s; i >= w; i--)
if (m[i - w] == 1)
m[i] = 1;
}
for (i =
s;; i--)
if (m[i] >
0) break;
printf("%d\n", i);
}