Задача о ранце без стоимости #764573

Привет. Я сломался. Есть некое множество чисел в таблице, из которых надо оптимально выбрать значения которые в сумме дадут <= необходимую сумму. Нужен алгоритм для восьмерки. Нашел вот это , но что-то ничерта не могу понять поскольку для 7.

Жадным алгоритмом попробуйте: упорядочить по убыванию, добавлять очередное, если возможно.

А пример есть?

Задача о ранце без стоимости подобна задаче о ранце со стоимостью, только... Без только, это она и есть.

Какой еще пример нужен: там 5 строчек кода. Если на тестовых примерах будет плохо подбирать, тогда нужно будет смотреть, как улучшить (литературы по ранцу полно. На форуме есть участник NZ или NS - не помню - который с ранцем плотно возился). Вы для начала озвучьте порядок количества чисел.

К примеру 40 различных чисел, 123, 434, 5943, 334, 4322, 4343, 4445, 4303, итд, из них надо выбрать числа которые в сумме дадут <= 24500

Пока на ум приходит Цикл в Цикле для каждого значения.

Пусть числа хранятся в ТЗ.

необязательно будет лучший результат

Ну отберет этот цикл из первых чисел, результат не оптимален.

почему из первых ? ты внимательно читал ?

Пусть задана пара (S, t), где S = {x1, x2, …, xn} представляет собой множество положительных целых чисел, а t — положительное целое число. Требуется отыскать среди подмножеств множества S, сумма которых не превосходит t, такое, у которого сумма ближе всего к t. Пусть |S| = n. Обозначим (k, w) — задачу, в которой имеется k первых чисел из S и нужно набрать сумму w. Таким образом исходная задача — это задача (n, t). Для решения задачи построим таблицу T[n, t + 1], в клетку T[i, j] которой будем записывать оптимальное решение задачи (i, j). Первый столбец заполним нулями. Первую строку заполним сначала нулями, а начиная с клетки (1, x1) — числами x1. Клетку T[i, j] (i, j > 1) будем заполнять по правилу: Если j ? xi > 0, то y := T[i ? 1, j ? xi], иначе y := 0; T[i, j] := max(T [i ? 1, j], y + xi)

нужно косарь, числа 970, 960, 40, 20

вот еще. о гугл. ты могуЧ.

ну или вот 1 в 1. const     for j := M[1] to Ves do       for i := 1 to N do         begin     for j:= Ves downto 1 do       if T[j]> Cmax then end.

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

100500 :). математический алгоритм 1. Знаю что в битах обработках будет быстрее

вот еще можно почитать а так гуглить можно вечно :)

харош уже. все хотели просто пофлеймить, а ты вариантов накидал аки профессор. ТС вообще сказал, что "алгоритм для 77 сложна, дайти на 8ку"

это было к . вопрос по оптимизации и скорости получение результата :) Да я себе заметки тут оставил :)

Будет лучший вариант если исходное множество - матроид

К сожалению, ранец не матроид. Матроиды вообще нынче редки :-)