Задача на записи., Все возможные варианты покупки Опции

[Deluxweb]

Задача такая:
Дана запись со структурой (скажем с файла F1)
Товар
Цена
Количество
С клавиатуры вводится сумма денег S, что есть у покупателя

надо вывести в файл F2 все возможные полностью или частично удовлетворяющие варианты в границах суммы S

может кто сталкивался или видел что-то похожее...

задача с рюкзаками похожа чем то, но мне не додуматься, как ее довести до этой задачи с товаром...

Помогите чем можете, буду очень признателен.

Сообщение отредактировано: Deluxweb - 1.05.2005 16:30

[volvo]

Deluxweb, что-то в задании настораживает... В частности - вот это:

надо вывести в файл F2 все возможные полностью или частично удовлетворяющие варианты в границах суммы S

Что значит "частично удовлетворяющий вариант"? Насколько я понимаю, "полностью удовлетворяющим вариантом" можно считать тот, при котором сумма денег S больше чем общая стоимость выбранного товара. Объясните мне в таком случае, что значит "частично"...

[Deluxweb]

Deluxweb, что-то в задании настораживает... В частности - вот это:

Что значит "частично удовлетворяющий вариант"? Насколько я понимаю, "полностью удовлетворяющим вариантом" можно считать тот, при котором сумма денег S больше чем общая стоимость выбранного товара. Объясните мне в таком случае, что значит "частично"...

Согласен кривовато звучит...
Полностью это имелось в виду товар купленный ровно на сумму S а частично - на сумму меньше чем сумма S
но так как там стоит ИЛИ все сводиться к тому чтобы найти все варианты при которых цена покупки ровна или меньше суммы S

Сообщение отредактировано: Deluxweb - 1.05.2005 18:10

[volvo]

Согласен кривовато звучит...
Полностью это имелось в виду товар купленный ровно на сумму S а частично - на сумму меньше чем сумма S
но так как там стоит ИЛИ все сводиться к тому чтобы найти все варианты при которых цена покупки ровна или меньше суммы S

Тогда вот так (только учти, что это - совершенно неоптимизировано, и при бОльших значениях будет выполняться ОЧЕНЬ долго):

const
  n = 5;
  s: longint = 150; { сумма на руках у пользователя }
type
  arrType = array[1 .. n] of integer;
const
  { исходные значения }
  count: arrType = (1, 1, 3, 7, 8);
  price: arrType = (8, 3, 5, 6, 9);

var
  found, total: longint;

{ подсчет суммы, необходимой в каждый момент }
function get_sum: longint;
var
  s: longint;
  i: integer;
begin
  s := 0;
  for i := 1 to n do
    s := s + count[i] * price[i];
  get_sum := s;
  inc(total);
end;

{ здесь будет вывод в файл }
procedure print;
var i: integer;
begin
  for i := 1 to n do
    { P - номер товара, A - его количество }
    write('p:', i:2, ' a:', count[i]:3, '':2);
  writeln;
  inc(found);
end;

{ а вот и "сердце" программы }
procedure main(k: integer);
var
  i, T: integer;
begin
  if k = n then begin
    T := count[k];
    for i := T downto 0 do begin
      count[k] := i;
      if get_sum <= s then print;
    end;
    count[k] := T;
  end
  else begin
    T := count[k];
    for i := T downto 0 do begin
      count[k] := i; main(k + 1)
    end;
    count[k] := T
  end
end;

begin
  found := 0; total := 0;
  main(1);

  { это для статистики (сколько перебрали, и сколько подошло) }
  writeln('found/total = ', found, '/', total, '=', found/total:10:5);
end.

Просто напросто тебе придется читать файл с данными, и записывать в массив count количества товаров, в массив price их цены, и присваивать количество переменной N, алгоритм будет работать (но очень долго )