Задача о вероятности, Задача полностью решена Опции

[Zxzc]

Помогите решить задачу:
Мальчик накапливал в копилке деньги. Однажды он увидел в магазине некий товар стоимостью S.
Дело в том что копилка заполнена не до конца, а разбивать ее можно лишь при 100% уверенности,
что количества денег будет достаточно. Но он не помнит сколько монет какого достоинства клал в копилку. Также известна масса пустой копилки и, конечно, текущая масса.
Известны соотношения Номинал <--> Масса монеты. Нужно определить минимальную вероятность и если она равна 100% вывести:"Вперед!!!!!!!!!!!"
Я решил задачу, получилось что количество вложенных циклов равно количеству разновидностей монет.
Проблема в том, что заранее не известно число разновидностей
монет. Также важно, что монеты, номинал которых больше, не всегда тяжелее. Но это не проблема...
Препод предложил идти через двумерный массив(M,N его - большие числа). И каким-то замысловатым способом из 2-х массивов(в первом - номиналы, во втором - массы) получаем массив [m,n]-й элемент к-рого - минимальное кол-во денег... Потом он сам запутался...
Мда.. Давно я так не попадался...

Сообщение отредактировано: Zxzc - 13.05.2006 21:44

[Zxzc]

монет с этим миниальным удельным достоинством нельзя набрать целое количество так чтобы они полностью покрыли массу монет в копилке

А нам это надо? Удельное достоинство изначально подразумевает не целые числа.
Мы ищем не минимальное количество медяшек, а их сумму!
Или я не прав?
А! Я наконец-то понял суть проблемы. Раньше я трактовал ее несколько иначе!

Сообщение отредактировано: Zxzc - 9.05.2006 16:16

[Lapp]

А! Я наконец-то понял суть проблемы. Раньше я трактовал ее несколько иначе!

Лучше поздно, чем никогда!

Сейчас я перечитал свой пост - не очень-то ясно написано.. . Переписывать (без специальных запросов), пожалуй, не буду, но немного добавлю.

Общий вес монет задается константой S.
Набор монет задается в типизированной константе Coins. В каждой записи указываются номинал монеты (v, от слова value) и вес (w, от слова weight). Число записей (число различных типов монет) задается константой M (в моем примере 6 разичных монет достоинством 1, 2, 5, 10, 20 и 50 единиц (копеек ), соответственно весом 4, 8, 20, 3, 6 и 2 единицы (грамм). Монеты могут идти в любом порядке.

Если невозможно подобрать комбинацию монет с заданным весом S, то программа выдает фразу "No match found" (совпадение не найдено).
Если найдена искомая комбинация монет (согласно логике поиска, она обязательно минимальная [см. P.S.]), то выводится соответствующая сумма в единцах (копейках).

Я думаю, было бы полезно выводить и способ, которым набрана данная сумма. Для этого нужно добавить одну строчку, что я сейчас и сделаю...
[в течение некоторого времени ожесточенно колотит по клаве, чешет репу и наливает чай]
...сделал! В результате получилась фактически новая версия .

Кроме прочего, старая версия странным образом глючила.. Я так и не смог разобраться, в чем дело, поскольку после добавления определенных переменных и операторов для отладки она глючить перестала, вроде. Если кто-то заметит глюки, прошу сказать мне о них.

Еще добавлю, что результаты (зависимость минимально возможной суммы от веса) выглядят довольно забавно . Радостные предвкушения от ощущения тяжести руках может смениться разочарованием (например, при весе 100), а легкость (вес 5) может дать неплохой навар!
Распределение монет по весам я взял чисто от балды, оно не имеет к обычной реальности никакого отношения (думаю, это и не требовалось). Рекомендую поиграться с ним, чтобы понять суть проблемы..

И последнее: хочу обратить внимание на пользу рекурсии. Фактически, все решение укладывается в функцию MinFill. Все остальное - подготовка ряда значений и весов монет. Если принять, что он уже упорядоченный и без лишних значений - прога уменьшится драматически .

Итак, вот новая версия. Кстати, она запрашивает вес монет с клавиатуры..

const
  M=6;    {Vsego tipov monet}

type
  Int=integer;
  tCoin=record
    v,w:Int;  {Value and Weight of a coin}
  end;
  tCoins=array[1..M]of tCoin;

var
  S:Int;   {Ves vseh monet v kopilke}
  Coin:tCoin;
  i,j,x,y:Int;

const
  N:Int=M;
    {All known coin kinds}
  Coins:tCoins=(
    (v:1;w:4),
    (v:2;w:8),
    (v:5;w:20),
    (v:10;w:3),
    (v:20;w:6),
    (v:50;w:2));
  Scale:Int=1;
  L:Int=0;
  Total:Int=0;

function MinFill(c,R:Int):boolean;
    {c - coin number as it appeares in Coins array}
    {R - remaining coins total weight}
var
  a:Int;
  b:boolean;

  function CountDown:boolean;
  begin
      {Postepenno umenjshaem koli4estvo melkih monet}
    while (a>=0)and not MinFill(c+1,R-a*Coins[c].w) do Dec(a);
    CountDown:=a>=0
  end;

begin
  with Coins[c] do begin
    a:=R div w;
    b:=(R mod w=0)or(c<N)and CountDown;
    MinFill:=b;
    if b then begin
      Inc(Total,a*v);
      WriteLn(a:3,' coins of value=',v:3,',  (total value=',v*a:5,')',',  weight=',w:3,',  (total weight=',w*a:5,')')
    end
  end
end;

begin
    {Podbiraem shkalu, 4toby udelnye stoimosti byly celymi}
  for i:=1 to N do with Coins[i] do
    if ((v*Scale) mod w)>0 then Scale:=Scale*w;

    {Uporyado4ivaem}
  for i:=1 to N-1 do with Coins[i] do begin
    x:=v*Scale div w;
    y:=v;
    for j:=i+1 to N do with Coins[j] do if x>v*Scale div w then begin
      Coin:=Coins[i];
      Coins[i]:=Coins[j];
      Coins[j]:=Coin
    end
  end;

    {Ubiraem lishie (c odinkovymi udelnymi stoimostyami)}
  i:=1;
  while i<N do with Coins[i+1] do begin
    while (i<N)and(Coins[i].v*Scale div Coins[i].w=v*Scale div w) do begin
      if Coins[i].v<v then x:=i+1 else x:=i;
      for j:=x to N-1 do Coins[j]:=Coins[j+1];
      Dec(N)
    end;
    Inc(i)
  end;
  Write(#13,#10,'Type in the total coins weight: '); ReadLn(S);

  {Vpered!}
  if MinFill(1,S) then WriteLn('Minimal Total : ',Total) else WriteLn('No match found');
  ReadLn
end.

P.S.
Моя фраза об обязательной минимальности резульата на самом деле нуждается в доказательстве. Я уверен в этом довольно сильно, но руку на отсечение пока не дам... Кто это докажет/опровергнет?