Решила (кое-как) задачу с помощью ДП, но как-то тупо, тройным циклом, полностью заполняя всю трёхмерную таблицу.
Можно ли не всю таблицу заполнять, или вообще двумерной таблицей обойтись?
Задача NP-полная, псевдополиномиальная.
Условие.
Дано N целых положительных слагаемых, целое положительное число B.
Вопрос.
Набрать сумму, минимально отклоняющуюся от B (с недостатком). Если таких наборов несколько, выбрать решение с минимальным числом слагаемых.
Или так: набрать заданный вес как можно ближе по недостатку, используя минимальное число камней.
Решение.
Функция T[i,j,k] равна 1, если вес j можно набрать первыми i слагаемыми, используя не более k слагаемых.
Иначе - нулю. Три параметра у функции, вот уже и трёхмерная таблица.
Реккурентные соотношения.
Если вес i-го слагаемого M[i] не превосходит набираемой суммы j, то
T[i, j, k]:= max{T[i - 1, j, k], T[i - 1, j - M[i], k-1]}
иначе T[i, j, k]:= T[i - 1, j, k]
Консольное приложение в Делфи7. Не могу вернуть комментариям читаемый вид, увы.
Вроде работает. Выдает ближайший к заданной сумме минимальный набор.
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
const
N=5; //êîëè÷åñòâî ñëàãàåìûõ
Ves=16; //íàáèðàåìûé âåñ
Ks=4; //îãðàíè÷åíèå íà ÷èñëî ñëàãàåìûõ
var
M: array[1..N] of integer;//âåñà ñëàãàåìûõ
//T= 1 åñëè âåñ íàáðàí, T= 0 - â ïðîòèâíîì ñëó÷àå
//0..N - èç ñêîëüêè ïåðâûõ ñëàãàåìûõ ìîæíî íàáèðàòü ñóììó
//0..Ves - êàêîé âåñ íóæíî íàáðàòü
//0..Ks - ñêîëüêî ñëàãàåìûõ ìîæíî âçÿòü
T:array[0..N,0..Ves,0..Ks] of byte;
sum,i,j,v,k,kmin:integer;
begin
M[1]:= 4; M[2]:= 4; M[3]:= 3; M[4]:= 7; M[5]:= 3;
//íåíóëåâîé âåñ èç 0 ñëàãàåìûõ íå íàáåðåøü
for j := 1 to Ves do
for k := 1 to Ks do
T[0, j, k] := 0;
for i := 1 to N do
for j:=1 to Ves do
T[i, j, 0] := 0;
for j := 1 to Ves do
T[0, j, 0] := 0;
//íóëåâîé âåñ âñåãäà ìîæíî íàáðàòü
for i:= 0 to N do
for k:=0 to Ks do
T[i, 0, k] := 1;
for i := 1 to N do begin
for j := 1 to Ves do begin
for k:=1 to Ks do
//i-å ñëàãàåìîå íå ïðåâîñõîäèò íàáèðàåìóþ ñóììó
if j >= M[i] then begin
//i-å ñëàãàåìîå â ðàçáèåíèå íå âõîäèò
if T[i - 1, j, k]> T[i - 1, j - M[i], k-1] then
T[i, j, k]:= T[i - 1, j, k]
//äîáàâëÿåì i-å ñëàãàåìîå ê ðåøåíèþ
else T[i, j, k]:= T[i - 1, j - M[i], k-1]; end
//i-å ñëàãàåìîå áîëüøå íàáèðàåìîé ñóììû
else T[i, j, k]:= T[i - 1, j, k];
end;
end;
for j:= Ves downto 1 do
//ìîæåì íàáðàòü ñóììó j ñ îãðàíè÷åíèåì íà Ks ñëàãàåìûõ
if T[N, j, Ks] = 1 then
begin
//èùåì ðàçáèåíèå j íà ìèíèìàëüíîå ÷èñëî ñëàãàåìûõ
for i:= Ks downto 1 do
if T[N, j, i]=1 then k:=i;
kmin:=k;
//âîññòàíàâëèâàåì ðàçáèåíèå j íà ìèíèìàëüíîå ÷èñëî ñëàãàåìûõ
sum:= j; v:=0;
for i:= N downto 1 do
begin
//i-å ñëàãàåìîå íå âîøëî â ðàçáèåíèå
if (T[i, sum, k] = T[i - 1, sum, k]) or (sum=0)then
writeln (i,'---No')
//i-å ñëàãàåìîå âîøëî â ðàçáèåíèå
else if sum>0 then
begin
writeln (i,' ',M[i]);
//óìåíüøèëè ñóììó
sum := sum - M[i];
v:=v+M[i];
//óìåíüøèëè êîëè÷åñòâî èñïîëüçóåìûõ ñëàãàåìûõ
k:=k-1;
end;
end;
break;
end;
writeln('summa=',v, ' count=', kmin);
readln;
end.
, сообразила, как сократить число параметров до двух.
То ли ДП тяжело даётся, то ли на работу после отпуска тяжело выходить. А вот если выкинуть эти массивы, и писать честной-благородной рекурсией, то даже думать не нужно.
да все было бы просто если бы так.... на 1 января все нормально закупили и вернули но не продали штучно....только финансово... а нам надо это в штуках)))) 