Добрый вечер.
У иеня тут интересная задача есть и один умный человек сказал что для ее решения нужно воспользоваться рюкзачным алгоритмом. Просветите мене темного плиз про этот алгоритм с походным названием.
Здравствуйте, Аноним, Вы писали:
А>У иеня тут интересная задача есть и один умный человек сказал что для ее решения нужно A>воспользоваться рюкзачным алгоритмом. Просветите мене темного плиз про этот алгоритм с походным названием.
По русски это называется задачей о ранце:
Русскоязычных источников я не знаю, а на английском
можно посмотреть по ссылке:
The knapsack problem has well-known methods to solve it,
among which are branch-and-bound and dynamic programming.
Здравствуйте, Аноним, Вы писали:
А>Добрый вечер. А>У иеня тут интересная задача есть и один умный человек сказал что для ее решения нужно воспользоваться рюкзачным алгоритмом. Просветите мене темного плиз про этот алгоритм с походным названием.
Задача формулируется примерно так:
— есть рюкзак известного обьема
— есть набор вещей — каждая известного обьема (обьемы уникальны). Некоторые из них упакованы у рюкзак
— узнать какие вещи упакованы в рюкзак.
Проблема в том, что рюкзак упаковать — легко, а вот узнать что туда напаковано — не очень... Причем некоторые варианты данной задачи — NP-полные.
Вот тебе цитата из "Applied Cryptography" которая все это рассматривает более подробно.
19.2 Knapsack Algorithms
------------------------
The first algorithm for generalized public-key encryption was the knapsack algorithm developed by Ralph Merkle and Martin Hellman [713, 1074]. It could only be used for encryption, although Adi Shamir later adapted the system for digital signatures [1413]. Knapsack algorithms get their security from the knapsack problem, an NP-complete problem. Although this algorithm was later found to be insecure, it is worth examining because it demonstrates how an NP-complete problem can be used for public-key cryptography.
The knapsack problem is a simple one. Given a pile of items, each with different weights, is it possible to put some of those items into a knapsack so that the knapsack weighs a given amount? More formally: Given a set of values M1, M2,..., Mn , and a sum S, compute the values of bi such that
S = b1M1 + b2M2 + ...+ bnMn
The values of bi can be either zero or one. A one indicates that the item is in the knapsack; a zero indicates that it isn’t.
For example, the items might have weights of 1, 5, 6, 11, 14, and 20. You could pack a knapsack that weighs 22; use weights 5, 6, and 11. You could not pack a knapsack that weighs 24. In general, the time required to solve this problem seems to grow exponentially with the number of items in the pile.
The idea behind the Merkle-Hellman knapsack algorithm is to encode a message as a solution to a series of knapsack problems. A block of plaintext equal in length to the number of items in the pile would select the items in the knapsack (plaintext bits corresponding to the b values), and the ciphertext would be the resulting sum. Figure 19.1 shows a plaintext encrypted with a sample knapsack problem.
The trick is that there are actually two different knapsack problems, one solvable in linear time and the other believed not to be. The easy knapsack can be modified to create the hard knapsack. The public key is the hard knapsack, which can easily be used to encrypt but cannot be used to decrypt messages. The private key is the easy knapsack, which gives an easy way to decrypt messages. People who don’t know the private key are forced to try to solve the hard knapsack problem.
Superincreasing Knapsacks
-------------------------
What is the easy knapsack problem? If the list of weights is a superincreasing sequence, then the resulting knapsack problem is easy to solve. A superincreasing sequence is a sequence in which every term is greater than the sum of all the previous terms. For example, {1, 3, 6, 13, 27, 52} is a superincreasing sequence, but {1, 3, 4, 9, 15, 25} is not.
The solution to a superincreasing knapsack is easy to find. Take the total weight and compare it with the largest number in the sequence. If the total weight is less than the number, then it is not in the knapsack. If the total weight is greater than or equal to the number, then it is in the knapsack. Reduce the weight of the knapsack by the value and move to the next largest number in the sequence. Repeat until finished. If the total weight has been brought to zero, then there is a solution. If the total weight has not, there isn’t.
____________________
God obviously didn't debug, hasn't done any maintenance, and no documentation can be found. Truly amateur work.
Здравствуйте, WolfHound, Вы писали: WH>Во первых представься.
Ну вроде представился, извините сразу не догодался. WH>Во вторых задачу в студию.
Вообще я задачу сам хотел решить, но я нежадный поделюсь со всеми:
Есть у нас много-много чисел и надо среди них наити сумму нескольких чисел такую, что бы она делилась на данное нам число N. Проблема в том что стоит ограничение времени и перебор не поможет, нужно что то другое придумать. WH>ЗЫ А че умный челевек не колется?
Умный человек сказал, что у него есть книга про этот алгоритм . Естессно я у него книгу попросил. Он сказал :'OK,я тебе ее дам'. И конечно этои книги у него шас нет говорит, что вроде кому-то книгу дал а кому — непомнит. лирическое отступление:
Убивать таких надо блин, книги берут а потом себе зажимают, у меня так скоко дисков пропало и не посчитать!!!
Спасибо всем за англицкие тексты, хотя я в англицком полный швах(патриотические чувства мешают мне его учить) но есть и переводчики.
Здравствуйте, Аноним, Вы писали:
А>Добрый вечер. А>У иеня тут интересная задача есть и один умный человек сказал что для ее решения нужно воспользоваться рюкзачным алгоритмом. Просветите мене темного плиз про этот алгоритм с походным названием.
Здравствуйте, Nelud, Вы писали:
N>Есть у нас много-много чисел и надо среди них наити сумму нескольких чисел такую, что бы она делилась на данное нам число N. Проблема в том что стоит ограничение времени и перебор не поможет, нужно что то другое придумать.
Конечно, ее можно решать и полным перебором (это я в защиту умного человека), но, как правильно было отмечено — времени может не хватить.
Будем искать множество индексов чисел в исходной последовательности. Рассмотрим n чисел a_1, a_1+a_2, ..., a_1+...+a_n, и остатки от деления их на n: r_1, r_2, ..., r_n. Если найдется число i, такое что r_i=0, то множество{1,2,...,i} — искомое. Если нет, то найдутся i, j: r_i=r_j, (по принципу Дирихле!) т.к. остатки r_1, r_2, ..., r_n не принимают более n-1 различных значений. Тогда множество {i+1,...,j} — ответ.
Из приведенных математических выкладок ( ) следует, что искомое множество индексов существует всегда, и существует хотя бы одно множество, элементы которого идут подряд. А вот если бы нам нужно было отыскать такие числа, сумма которых была бы n (а не делилась на n), то задача из линейной превратилась бы в NPC!
Подчеркивание означает индекс (ну, как в ТеХ-е).
Эта задача была предложена в 95 году на всеукраинской олимпиаде (школьников) по информатике.
Здравствуйте, TheGrey, Вы писали:
TG>Будем искать множество индексов чисел в исходной последовательности. Рассмотрим n чисел a_1, a_1+a_2, ..., a_1+...+a_n, и остатки от деления их на n: r_1, r_2, ..., r_n. Если найдется число i, такое что r_i=0, то множество{1,2,...,i} — искомое. Если нет, то найдутся i, j: r_i=r_j, (по принципу Дирихле!) т.к. остатки r_1, r_2, ..., r_n не принимают более n-1 различных значений. Тогда множество {i+1,...,j} — ответ.
OK, но если у нас n чисел и надо делить на k где k>n то тогда ...
Здравствуйте, Nelud, Вы писали:
N>OK, но если у нас n чисел и надо делить на k где k>n то тогда ...
Тогда, в общем случае, задача будет очень похожа на NP-сложную. Я не смог пока этого доказать. Можно посмотреть книгу Гери и Джонсона, в которой описано много известных задач и дана мотивация их принадлежности/непринадлежности классам NPC/NPH. Однако, в некоторых случаях, эту задачу можно будет решить эффективно. Например, при N>=K, или при K=N+1 можно реализовать квадратичный алгоритм, который будет выкидывать каждый из элементов исходного множества, и потом применять описанную идею для массива без элемента (то же самое и для K=N+2, K=N+3...; только выкидывать прийдется по два, три, ... элемента, что будет каждый раз увеличивать сложность на порядок).
Так что, похоже, на счет рюкзачного алгоритма умный человек был прав. Особенно если он имел ввиду backtracking. В таком случае нужно смотреть те материалы, которые были предложены.
) следует, что искомое множество индексов существует всегда, и существует хотя бы одно множество, элементы которого идут подряд. А вот если бы нам нужно было отыскать такие числа, сумма которых была бы n (а не делилась на n), то задача из линейной превратилась бы в NPC! 