>применение задачи о рюкзаке ( ранце)
Вот вам и применение. Вчера ко мне прямо с утра прибежали, срочно
и важно: набрать сумму по какой-то хрени... типа по поставщикам...
Пришлось вспомнить эту задачку и "с блеском" выручить людей.
Вечером я для интереса сделал эту хрень на VBA (рекурсией). Кстати,
входные данные реальные и просто супер для тестирования - такие сам
не придумаешь. Чудовищно загадочно, что нужная сумма набралась.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
Private a, N
Const Summa = 6243120 '--надо набрать эту сумму
Sub Main()
a = Array( _
6110475, 3765608, 2782904, 2709852, 1916507, 1777094, 1687988, _
1389334, 1097480, 958193, 709066, 626633, 609345, 463030, 429227, _
418305, 387644, 331857, 321041, 212298, 184552, 121218, 23398 _
) '''массив должен заполняться по убыванию!
N = UBound(a)
deef a, 0 , 0
End Sub
Sub deef(ByVal ar, ByVal sm, ByVal r)
Dim i, j, res, br
For i = r To N
If ar(i) <> 0 Then
If ar(i) + sm = Summa Then
For j = 0 To N
If ar(j) = 0 Or j = i Then res = res & a(j) & vbCrLf
Next
Debug.Print res
MsgBox res
'End 'анкоммент! если достаточно найти только одну комбинацию!
ElseIf ar(i) + sm < Summa Then
br = ar
br(i) = 0
deef br, sm + ar(i), i + 1
End If
End If
Next
End Sub
А теперь сравните с быстродействием t-скуль кода от Paul Chabinsky
(как известно, мой аналогичный t-скуль скрипт работает немного
медленнее, чем его; плюс, я так и не сделал (поленился) корректный
выход из бесконечного цикла). КОРОЧЕ, ДАВАЙТЕ МЕРЯТЬСЯ ПИСЬКАМИ!
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
begin tran
set nocount on
declare @summ decimal( 9 , 2 )
set @summ = 6243120 ---<<<<<<<<<<< СУММА
create table #t (
id int identity( 1 , 1 ) primary key,
amount money
)
insert #t (amount)
select 23398 union all
select 121218 union all
select 184552 union all
select 212298 union all
select 321041 union all
select 331857 union all
select 387644 union all
select 418305 union all
select 429227 union all
select 463030 union all
select 609345 union all
select 626633 union all
select 709066 union all
select 958193 union all
select 1097480 union all
select 1389334 union all
select 1687988 union all
select 1777094 union all
select 1916507 union all
select 2709852 union all
select 2782904 union all
select 3765608 union all
select 6110475
create table #hash(
a int, --Точка начальная
b int, --Точка конечная
deep int, --Количество промежуточных пунктов
summ decimal( 9 , 2 ), --Суммарная длинна пути
offset decimal( 9 , 2 ), --Длинна последнего отрезка пути
path varchar( 500 ) primary key --Строковое выражение пути, ввиде длинны ребер графа через знак плюса, в расчетах не участвуюет
)
insert into #hash
select t1.id,t2.id, 2 ,t1.amount+t2.amount,t2.amount, convert(varchar,t1.id)+'.'+convert(varchar,t2.id)
from #t t1, #t t2
where t1.id<t2.id and t1.amount+t2.amount<=@summ
declare @deep int, @max_deep int
select @deep = 1 , @max_deep = (select count(*) from #t)
while @deep<=@max_deep
begin
--Увеличиваем количество пунктов в пути
select @deep = @deep+ 1
--Вставляем пару значений в конец пути
insert into #hash
select h1.a a,h2.b b,h1.deep+ 1 deep,h1.summ+h2.offset summ,h2.offset offset, h1.path+'.'+convert(varchar,h2.b) path
from #hash h1 inner join #hash h2 on h1.a<h2.b and h1.b = h2.a and h1.deep = @deep and h2.deep = 2 and h1.summ+h2.offset<=@summ
--Если вставки не было выйти из цикла
if @@rowcount<= 0
break
--Удаляем бесперспективные куски пути, здесь можно еще поиграца в поисках производительности
delete from #hash where b<=@deep and summ<>@summ
end
select path from #hash where summ = @summ order by a,b,path
rollback tran
