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

[Zxzc]

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

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

[Lapp]

Заинтересовала меня эта задачка тоже.. Мужики, вы зря не слушаете volvo - рекурсия тут решает все проблемы в несколько строчек. План примерно такой:

1. Подбираем удобную шкалу, чтоб удельные стоимости (УС) были целыми.
2. Упорядочиваем все типы монет в порядке возрастания УС.
3. Убираем лишние монеты (все, что можно набрать 2-ками весом в 2г, можно набрать и копейками весом 1г - значит, двушки не нужны)
4. Делим полный вес на вес монеты с наименьшей УС (№1). Если их количество вышло нецелым, вычитаем их массу из начальной массы, убираем монету №1 из расмотрения и повторяем то же самое с новой массой и новым набором монет. Если неудачно - убираем одну монету №1 и повторяем. И так до тех пор, пока не будет достигнуто соответствие либо не будет безрезультатно перебрано все.

Ниже даю код. Ошибок, вроде, нет, но проверял не очень тщательно. Если есть вопросы - пишите..

const
  M=6;    {Vsego tipov monet}
  S=31;   {Ves vseh monet v kopilke}

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

var
  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:23));
  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;

  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;
    MinFill:=(R mod w=0)or(c<N)and CountDown;
    Inc(Total,a*v)
  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;

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