2103. Рюкзак

Вася собрался в поход с друзьями-программистами и решил ответственно подойти к выбору того, что он возьмёт с собой. У Васи есть n вещей, которые он мог бы взять с собой в рюкзаке. Каждая вещь весит 1 килограмм. Вещи обладают разной “полезностью” для Васи.

Поход предстоит весьма длинный, и Вася хотел бы носить рюкзак весом не более w килограмм.

Помогите ему определить максимальную суммарную “полезность” предметов в его рюкзаке при весе рюкзака не более w килограмм.

Вход. В первой строке находятся целые числа w и n (1 ≤ w, n ≤ 20). Во второй строке записаны n целых чисел c_i (1 ≤ c_i ≤ 1000) – “полезности” каждой из вещей.

Выход. Выведите максимальную суммарную “полезность” предметов, которые Вася может взять с собой.

Пример входа	Пример выхода
2 3 1 5 3	8

РЕШЕНИЕ

жадность

Анализ алгоритма

Воспользуемся жадным подходом. Отсортируем вещи по невозрастанию полезности. Поскольку вес каждой вещи 1 килограмм, то Васе следует взять min(w, n) самых полезных вещей.

Пример

Рассмотрим пример из условия задачи. Отсортируем по убыванию три заданные вещи. И возьмем две с наибольшей полезностью.

Реализация алгоритма

Читаем входные данные. Полезности вещей сохраняем в массиве cost.

scanf("%d %d", &w, &n);

cost.resize(n);

for(i = 0; i < n; i++)

scanf("%d",&cost[i]);

Сортируем полезности вещей по неубыванию.

sort(cost.begin(),cost.end(),greater<int>());

Суммируем полезности вещей.

s = 0;

for(i = 0; i < min(w,n); i++)

s += cost[i];

Выводим ответ.

printf("%d\n",s);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int w = con.nextInt();

int n = con.nextInt();

Integer cost[] = new Integer[n];

for(int i = 0; i < n; i++)

cost[i] = con.nextInt();

Arrays.sort(cost,Collections.reverseOrder());

int s = 0;

for(int i = 0; i < Math.min(w,n); i++)

s += cost[i];

System.out.println(s);

con.close();

}

}