Алгоритм выбора N предметов по цене

День добрый, уважаемые форумчане!
Столкнулся с такой задачей:
Например, у нас есть 4 предмета(может быть сколько угодно) и их цена
1 - 5p
2 - 10p
3 - 5p
4 - 10p
Задача стоит такая, выбрать отсюда предметы таким образом, чтобы они удовлетворяли условию: сумма выбранных предметов = 30%(+-5% (например) от общей суммы предметов.
В данном случае возможны такие комбинации: 1,3 и 2. ( В приоритете комбинация с меньшим кол-ов предметов)
Т.е нужно получить максимально близкую к N% от общей суммы комбинацию предметов.
Кто нибудь сталкивался с подобными алгоритмами?
Есть примеры решения/алгоритмов?

 

Да, спасибо большое)
поглядел алгоритмы, задача походит на задачу о ранце(в моем случае вес=цене), а если точнее то это скорей задача о суммах подмножеств
Вот только с ее реализацией на php все как-то не очень, попробовал прогнать через алгоритм задачи о ранце и задачи о суммах подмн., до 20 предметов считает быстро, 40 - уже медленно (7-10 сек), на 50 зависает
В моем случае будет в районе 100 предметов, боюсь не дождусь результата
Даже не знаю, что теперь делать (а точнее, в чем проблема скорости? алгоритма или php?)

 

Забыл совсем, вот, одна из реализаций задачи о рюкзаке (w - вес, v - цена, uid - это уже моя доп.инфа)
Для 20 считает ещё более-менее, дальше - хуже

Код (PHP):

1. <?php
2.  
3. define('COMMISSION', '10'); // (%) от общей суммы предметов
4.  
5.  
6. // генерируем тестовые наборы
7. for ($i = 0; $i < 20; $i++) {
8.     $num = rand(5, 50)/2;
9.     $data[] = ['w' => $num, 'v' => $num, 'uid' => rand(65479, 65499)];
10.     $solution[] = -1;
11. }
12.  
13. // сортировка по убыванию
14. usort($data, "customSort");
15.  
16. function customSort($a, $b) {
17.     return $a['w'] < $b['w'];
18. }
19.  
20. $totalSum = array_sum(array_column($data, 'v'));
21.  
22. /*
23.  * n: number of items
24.  * content: the maximum content of the knapsack 
25.  */
26.  
27. function knapsack($n, $content) {
28.  
29.     global $data;
30.     global $solution;
31.  
32.     if ($n == 0 || $content == 0) {
33.         return 0;
34.     } else {
35.         for ($i = $n - 1; $i >= 0; $i--) {
36.             if ($data[$i]['w'] > $content) {
37.                 $solution[$i] = 0;
38.                 return knapsack($n - 1, $content);
39.             } else {
40.                 if (($data[$i]['v'] + knapsack($n - 1, $content - $data[$i]['w'])) > knapsack($n - 1, $content)) {
41.                     $solution[$i] = 1;
42.                     return $data[$i]['v'] + knapsack($n - 1, $content - $data[$i]['w']);
43.                 } else {
44.                     $solution[$i] = 0;
45.                     return knapsack($n - 1, $content);
46.                 }
47.             }
48.         }
49.     }
50. }
51. $comis = COMMISSION * $totalSum / 100;
52.  
53. printf('You need to take things to the amount %s<br>', $comis);
54.  
55. $maxvalue = knapsack(20, $comis);
56.  
57. $sum = 0;
58.  
59. for ($i = 0; $i < 20; $i++) {
60.     if (1 == $solution[$i]) {
61.         printf("Item %d is selected.", $i);
62.         printf("{value : %d,weight : %d, uid: %d}", $data[$i]['v'], $data[$i]['w'], $data[$i]['uid']);
63.         echo "<br>";
64.         $sum += $data[$i]['v'];
65.     }
66. }
67. printf("Sum: %s, TotalSum: %s This %s percent<br>", $sum, $totalSum, $sum / $totalSum * 100);
68. printf("Maximum value is: %d", $maxvalue);
69. ?>

PHP, JavaScript, SQL и другой код пишите внутри тегов

Код ( (Unknown Language)):

1. [b]php][/b]Тут код[b][/[/b][b]code][/b][/color]