При помощи набора чисел получить заданное число

Дано: набор (множество) из n чисел: Ai .. An. Также дано некое число B.
Найти: такое подмножество из чисел Ai .. An, чтобы их сумма была наиболее близка к заданному числу B. Каждое число из набора можно использовать всего один раз.

P.S. Что-то похожее на задачу о рюкзаке, но не могу уловить связи... Прошу помощи.
P.S.S. Задачу не требуется решать именно множествами, устроят и массивы. Подскажите, в каком направлении копать?

Это и есть задача о рюкзаке. Вернее, задача об одномерном контейнере.

Возможно, но особенность в том, что в моем случае заданное число может быть превышено, т.е. сумма необходимых чисел из набора может быть как больше, так и меньше заданного числа, главное, чтобы их модуль разности был минимален.

Эта особенность - описательная, и на суть решения не влияет.

C-r-o-w, в разделе есть даже программа (моя) на паскале. Наиболее близкая сумма набирается с помощью динамического программирования.

Добавлено 05.03.11, 09:20
Сумма чисел в массиве, наиболее приближающаяся к необходимой

Ок, спасибо, буду разбираться

C-r-o-w, есть еще такой способ на мой взгляд достаточно универсальный поскольку позволяет варировать получаемым результатом в соответствии с нужными условиями:

1. получить все возможные различные выборки из данного набора
2. проанализировать разницу суммы элементов набора и контрольной суммы
3. вывести результат для требуемого условия

реализация такого подхода может быть такой:

type
  tarrint = array of integer;
 
  tnelem = record
    val: integer;
    ind: integer;
  end;
 
  tarrnelem = array of tnelem;
 
  telem = record
    arr: tarrnelem;
    delta: integer;
    gruppa: integer
  end;
 
  tarrelem = array of telem;
 
function generateASets(tmpA: tarrint): tarrelem;
{---------------------------------------------------}
{ Функция формирования всех возможных различных ... }
{ ... выборок из данного набора элементов           }
{---------------------------------------------------}
{ Параметры:                                        }
{   tmpA - массив с исходными данными               }
{---------------------------------------------------}
var
  tmpAInd: tarrint;
  i, n: integer;
  tmpEl: telem;
begin
  n:=high(tmpA) - low(tmpA) + 1;
  setlength(tmpAInd, n+1);
  for i:=0 to n do tmpAInd[i]:=0;
  while tmpAInd[n] <> 1 do
    begin
      i:=0;
      while tmpAInd[i] = 1 do
        begin
          tmpAInd[i]:=0; i:=i+1
        end;
      tmpAInd[i]:=1; tmpEl.delta:=0; tmpEl.gruppa:=1;
      for i:=0 to n-1 do
        if tmpAInd[i] = 1 then
          begin
            if tmpEl.arr = nil then
              setlength(tmpEl.arr, 1)
            else
              setlength(tmpEl.arr, high(tmpEl.arr) + 2);
            tmpEl.arr[high(tmpEl.arr)].val:=tmpA[i];
            tmpEl.arr[high(tmpEl.arr)].ind:=i;
            tmpEl.delta:=tmpEl.delta + tmpA[i]
          end;
      if tmpEl.arr <> nil then
        begin
          if result = nil then
              setlength(result, 1)
            else
              setlength(result, high(result) + 2);
          result[high(result)]:=tmpEl;
          setlength(tmpEl.arr, 0)
        end
    end;
  setlength(tmpAInd, 0)
end;
 
procedure sortArray(var tmpA: tarrelem; tmpUSort: boolean = true);
{---------------------------------------------------}
{ Функция упорядочивания полученных даных по за- ...}
{ ... данному направлению (возрастание/убывание)    }
{---------------------------------------------------}
{ Параметры:                                        }
{   tmpA - массив с исходными данными;              }
{   tmpUSort - признак направления сортировки       }
{---------------------------------------------------}
var
  i, tmpBuf: integer;
  tmpEl: telem;
  fl: boolean;
begin
  fl:=true;
  // сортировка по заданному по направлению (возрастание/убывание)
  while fl do
    begin
      fl:=false;
      for i:=low(tmpA) to (high(tmpA)-1) do
        if ((tmpA[i].delta > tmpA[i+1].delta) and tmpUSort) or
           ((tmpA[i].delta < tmpA[i+1].delta) and not tmpUSort) then
        begin
          tmpEl:=tmpA[i]; tmpA[i]:=tmpA[i+1];
          tmpA[i+1]:=tmpEl; fl:=true
        end
    end;
  // распределение групп с одинаковыми разницами ...
  // ... по отношению к проверяемой
  tmpBuf:=tmpA[low(tmpA)].delta;
  for i:=(low(tmpA) + 1) to high(tmpA) do
    if tmpA[i].delta <> tmpBuf then
      begin
        tmpA[i].gruppa:=tmpA[i-1].gruppa + 1;
        tmpBuf:=tmpA[i].delta
      end
    else
      tmpA[i].gruppa:=tmpA[i-1].gruppa
end;
 
function getACorrent(tmpSA: tarrint; tmpCS: integer; tmpD: boolean = true): tarrelem;
{---------------------------------------------------}
{ Функция получения даных, которые наиболее удов-...}
{ ...летворяют условиям поиска                      }
{---------------------------------------------------}
{ Параметры:                                        }
{   tmpSA - массив с исходными данными;             }
{   tmpCS - сумма с которой анализируются выборки;  }
{   tmpD - признак опредяляющий результат работы ...}
{       ... (отличие минимально или максимально)    }
{---------------------------------------------------}
var
  i: integer;
  tmpA: tarrelem;
begin
  tmpA:=generateASets(tmpSA);
  for i:=low(tmpA) to high(tmpA) do
    if tmpA[i].delta > tmpCS then
      tmpA[i].delta:=tmpA[i].delta - tmpCS
    else
      tmpA[i].delta:=tmpCS - tmpA[i].delta;
  sortArray(tmpA);
  // делаем выборку подходящих значений
  if tmpD then
    begin
      for i:=low(tmpA) to high(tmpA) do
        if tmpA[i].gruppa = tmpA[low(tmpA)].gruppa then
          begin
            if result = nil then
              setlength(result, 1)
            else
              setlength(result, high(result) + 2);
            result[high(result)]:=tmpA[i]
          end
        else exit
    end
  else
    begin
      for i:=high(tmpA) downto low(tmpA) do
        if tmpA[i].gruppa = tmpA[high(tmpA)].gruppa then
          begin
            if result = nil then
              setlength(result, 1)
            else
              setlength(result, high(result) + 2);
            result[high(result)]:=tmpA[i]
          end
        else exit
    end
end;

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

Прикреплённый файлrz_project.zip (3,36 Кбайт, скачиваний: 126)

http://acm.tju.edu.cn/toj/showp3162.html

И чёт я как-то вот дрогнул - спужался размерностей

Добавлено 06.03.11, 20:58
а так конечно... в теории... динамика и т.д.