Блог

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

Пример:

 items = [
    {
        id: 1
        price: 1000
    },
    {
        id: 2
        price: 3000
    },
    {
        id: 3
        price: 7000
    },
    {
        id: 4
        price: 2500
    },
    {
        id: 5
        price: 5000
    }
];
not_combinable_item_pairs = [
    {idA: 3, idB: 5}, 
    {idA: 1, idB: 2},
    {idA: 2, idB: 3},
];
 

В этом примере элемент 3 не может быть объединен с элементом 5 и т. Д…

То, о чем я думал до сих пор, заключается в том, что вы можете исключить все элементы, которые могут быть объединены с любым другим элементом, потому что они могут быть добавлены к любой комбинации.

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

Далее я просмотрел соединения, но не смог найти алгоритм, который решает проблему в целом. Я был бы признателен за любые предложения, идеи или ссылки на литературу по такого рода проблемам.

Всего есть

N (N-1)/2 — длина (исключения)

возможные пары, которые необходимо будет протестировать. Я ваш случай: 10-3 = 7.

Я сам поиграл с этим и придумал следующее:

 const items = [1000,3000,7000,2500,5000], res=[],
   n=items.length,
   na=[[4,2],[0,1],[1,2]],
   nas=na.map(e=>e.sort().join(" "));

for (let i=0;i<n;i  )
  for (let j=i 1;j<n;j  ){
 let k=i " " j;
    if(nas.indexOf(k)<0) res.push([k,items[i] items[j]]);}

console.log(res.sort((a,b)=>b[1]-a[1])); 

Я немного сократил ваш синтаксис: Я избавился от id свойства и использовал индекс элементов напрямую, но это лишь косметический момент. Очевидно, что мои индексы теперь начинаются с 0, а не с 1. Массив na («неприменимо») содержит запрещенные комбинации, не обязательно в любом порядке, и nas является их строковой версией, которую я создал для более быстрого поиска.

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

Обновить

Поскольку OP дал понять, что ищутся комбинации любой длины, я переписал свой фрагмент.

Очевидно, что общее количество комбинаций теперь

2^N — 1 — длина(исключения)

поскольку пустое множество («без элементов») исключается.

 const items = [1000,3000,7000,2500,5000], 
   res=[],
   n=items.length,
   na=[[2,4],[0,1],[1,2]];
   
function combine(arr,ex){
  const n=arr.length,res=[];
  function cc(iarr,j){ // "concat with sum"
    let jarr=iarr.concat(j);
    jarr.sum=(iarr.sum||0) arr[j];
    return jarr;
  }
  function cmb(idx,i){
    for (let j=i;j<n;j  )
      if(!na.some(([a,b])=>idx.indexOf(a)>-1amp;amp;b==j))
        cmb(res[res.length]=cc(idx,j),j 1)
  }
  cmb([],0); // start the recursive call chain here
  return res.sort((a,b)=>b.sum-a.sum);
}

let comb=combine(items,[]);
console.log(comb.map(e=>e.join(",") "=" e.sum),
            comb.length) 

В этой версии я использую рекурсивную функцию cmb() для перебора всех разрешенных комбинаций, отслеживания задействованных индексов и одновременного накопления суммы с помощью моей пользовательской функции cc() объединения.

combine() возвращает массив со всеми разрешенными комбинациями, отсортированными в порядке убывания их сумм.

Это проблема нахождения независимого множества с максимальным весом в графе (где not_combinable_item_pairs находятся ребра).

Насколько я понимаю, полиномиальные решения существуют только для некоторых специальных типов графов, в то время как в общем случае это NP-сложная задача.

Итак, чтобы получить точное решение, вам нужно проверить все подмножества (для N вершин существует 2 ^ N подмножеств).