Есть задача сумма подмножеств (кажется это Subset Sum Problem, но точно не уверена). Вот условие: 
Задано конечное множество А, положительные целые веса для каждого элемента множества А и положительный целый вес К. 
Существует ли такое подмножество множества А, что сумма весов его элементов равна К. 

Решила эту задачу точным экспоненциальным алгоритмом, а как приближенный написать не знаю. 
Вот код точного алгоритма: 

Подскажите, пожалуйста, как написать приближенный алгоритм. 
Сказали, что нужно просто отсортировать гири и в цикле набирать вес, как только вес набран, так выходить из цикла, попробовала так сделать - не получилось.  

Serfect, тот метод, что тебе посоветовали не может дать 100% результата. Например, есть отсортированный набор весов, искомый находится только путем суммы 3-го, 5-го и 7-го. При этом, сумма первого и второго меньше необходимой. Вопрос, как не перебирая все возможные варианты получить необходимый результат?

Необходимо найти набор весов максимально приближенный к заданному весу, либо равный ему, если это возможно. Получается, что идем по циклу отсортированных в порядке убывания весов, если вес первого предмета не превышает заданный, включаем его в набор, идем дальше, если вес первого предмета + вес второго меньше либо равен заданному, то добавляем второй предмет в выборку, а если их суммарный вес больше, то отбрасываем и переходим к следующему, и т.д. пока не наберем нужный вес, как только все набран (или предметы закончились) выходим из цикла. 

Правильно понимаю приближенный алгоритм?  

Serfect, однопроходный алгоритм даёт не лучший результат. Например:
требуемый вес - 10
набор гирь - 7 5 4 1
в твоём случае выберется 7 и 1 = 8, а лучше было бы 5, 4 и 1 = 10. так ?
получается, что набрав какой-то вес, начиная с первого элемента, нужно пробовать набирать другие варианты, начиная со 2-го элемента, 3-го и т.д. И в каком случае получится ближайший к требуемому вес, такой и выбирать, а не обязательно первый. Как-то так.

имхо надо выходить из цикла только при достижении полного совпадения.
а пока не нашли, хранить луший вариант и искать более лучший.

а это не np-полная задача, часом?

> надо выходить из цикла только при
достижении полного совпадения
а если его вообще не будет?

А что такое np-полная задача?

Ну значит перебирать все варианты. Когда варианты закончатся, вывести лучший, который мы сохранили.


NP-полная задача
Своими словами, задача, решаемая только полным перебором.
Верней, пока не найдено пути решения таких задач за полиномиальное время (то есть без полного перебора).
Если кто найдет способ решить такую задачу без полного перебора, нобелевская премия по математике обеспечена.  
Но я не уверен, что именно эта задача сводится к np-полной.

volatile, аааа. всё. понял. просто обычно большими буквами пишут P = NP...


  

borisbn, не доказано, что P = NP, ровно как и P != NP.

volatile, ага, по математике))