"Greedy" и монеты. Опции

[DarkWishmaster]

Привет.
Вот задача:
В кошельке находятся N монет и их общий вес G:
Каждая монета имеет свою цену и свой вес:
цена: вес:
1 1
5 2
10 3
25 4
50 5
Выяснить минимальную общую стоимость монет которая может находится в кошельке
например:
G=23 N=10
минимальная стоимость =68:
3 монеты по 1
1 монета по 2
и 6 монет по 3
вот мой код:

 
 Program P1; Uses Crt;
 type Matrice=array[1..3,1..5] of byte;
   var A,b:matrice;  R,G,N,i,Nb,j,Suma,max,L:integer;
   Begin  ClrScr;
    CheckEof:=True;
    a[1,1]:=1; a[1,2]:=5; a[1,3]:=10; a[1,4]:=25; a[1,5]:=50;
    a[2,1]:=1; a[2,2]:=2; a[2,3]:=3; a[2,4]:=4; a[2,5]:=5;
      writeln('Nr. monet'); readln(N);
     writeln('Wes'); readln(G);
      if (G div N>5) or (N>G)  then exit;
    Suma:=0;
    for i:=1 to 5 do
       if a[2,i]*N>G then begin Nb:=a[2,i]; break;   end;
     Max:=G div Nb;
      R:=G mod Nb;
        if R=0 then a[3,Nb]:=Max else begin
        i:=1;
        if R<N-Max then Max:=Max-1;
           a[3,Nb]:=Max;
          while (L<N) do  begin
            L:=0;
            if (a[3,i]+a[2,i+1]=G-Nb*max) and (a[3,i]+a[3,Nb]+1=N) then
              begin inc(i); a[3,i]:=a[3,i]+1; end else   a[3,i]:=a[3,i]+1;
             for j:=1 to Nb do
               L:=L+a[3,j];
            end;
          end;
 for i:=1 to 3 do begin
    for j:=1 to 5 do begin
     write(a[i,j],' ');
      if i=3 then Suma:=Suma+a[1,j]*a[3,j];
      end;
       writeln;
       end;
    writeln(Suma);
     readln;
   end. 

Он рабочий для параметром 10 23, 10 22, и ещё нескольких, и я уверен что есть способ более легкой для это задачи.

Сообщение отредактировано: DarkWishmaster - 24.03.2011 20:44

[Lapp]

Привет.
Вот задача:
В кошельке находятся N монет и их общий вес G:
Каждая монета имеет свою цену и свой вес:
цена: вес:
1 1
5 2
10 3
25 4
50 5
Выяснить минимальную общую стоимость монет которая может находится в кошельке
например:
G=23 N=10
минимальная стоимость =68:
3 монеты по 1
1 монета по 2
и 6 монет по 3
вот мой код:

 
 Program P1; Uses Crt;
 type Matrice=array[1..3,1..5] of byte;
   var A,b:matrice;  R,G,N,i,Nb,j,Suma,max,L:integer;
   Begin  ClrScr;
    CheckEof:=True;
    a[1,1]:=1; a[1,2]:=5; a[1,3]:=10; a[1,4]:=25; a[1,5]:=50;
    a[2,1]:=1; a[2,2]:=2; a[2,3]:=3; a[2,4]:=4; a[2,5]:=5;
      writeln('Nr. monet'); readln(N);
     writeln('Wes'); readln(G);
      if (G div N>5) or (N>G)  then exit;
    Suma:=0;
    for i:=1 to 5 do
       if a[2,i]*N>G then begin Nb:=a[2,i]; break;   end;
     Max:=G div Nb;
      R:=G mod Nb;
        if R=0 then a[3,Nb]:=Max else begin
        i:=1;
        if R<N-Max then Max:=Max-1;
           a[3,Nb]:=Max;
          while (L<N) do  begin
            L:=0;
            if (a[3,i]+a[2,i+1]=G-Nb*max) and (a[3,i]+a[3,Nb]+1=N) then
              begin inc(i); a[3,i]:=a[3,i]+1; end else   a[3,i]:=a[3,i]+1;
             for j:=1 to Nb do
               L:=L+a[3,j];
            end;
          end;
 for i:=1 to 3 do begin
    for j:=1 to 5 do begin
     write(a[i,j],' ');
      if i=3 then Suma:=Suma+a[1,j]*a[3,j];
      end;
       writeln;
       end;
    writeln(Suma);
     readln;
   end. 

Он рабочий для параметром 10 23, 10 22, и ещё нескольких, и я уверен что есть способ более легкой для это задачи.

Однако, ответ неверный. Для 23 и 10 верный ответ такой
1 - 0
5 - 7
10 - 3
25 - 0
50 - 0
Что дает минимум суммы 65.

[DarkWishmaster]

Однако, ответ неверный. Для 23 и 10 верный ответ такой
1 - 0
5 - 7
10 - 3
25 - 0
50 - 0
Что дает минимум суммы 65.

Ага, я ошибься. Извините.
Есть идеи как это сделать?