Я хотел бы найти наиболее эффективный способ заправки транспортного средства, в основном различные комбинации, чтобы удовлетворить вместимость транспортных средств

Question

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

Например: у меня автомобиль с вместимостью 10, у меня разные комбинации типов (атрибутов)места, которые могут заполнить автомобиль по-разному (по умолчанию амбулаторное или нормальное количество мест 1).Кроме того, каждая комбинация, которая не равна 10 (больше 10 удаляется), будет заполнена амбулаторной емкостью или просто обычным сиденьем.Вот так:

const a = [ {
 name: 'wheelchair',
 capacity: 0,
 total: 3
}, {
  name: 'walker',
  capacity: 2,
  total: 5
  }, {
  name: 'service animal',
  capacity: 2,
  total: 5
}];

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

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

Этот код был изменен из этого ответа https://stackoverflow.com/a/21640840/6025994

  // the power set of [] is [[]]
  if(arr.length === 0) {
      return [[]];
  }

  // remove and remember the last element of the array
  var lastElement = arr.pop();

  // take the powerset of the rest of the array
  var restPowerset = powerSet(arr);


  // for each set in the power set of arr minus its last element,
  // include that set in the powerset of arr both with and without
  // the last element of arr
  var powerset = [];
  for(var i = 0, len = restPowerset.length; i < len; i++) {

      var set = restPowerset[i];

      // without last element
      powerset.push(set);

      // with last element
      set = set.slice(); // create a new array that's a copy of set
      set.push(lastElement);
      powerset.push(set);
  }

  return powerset;
};

var subsetsLessThan = function (arr, number) {
  // all subsets of arr
  var powerset = powerSet(arr);

  // subsets summing less than or equal to number
  var subsets = new Set();
  for(var i = 0, len = powerset.length; i < len; i++) {

      var subset = powerset[i];

      var sum = 0;
      const newObject = {};
      for(var j = 0, len2 = subset.length; j < len2; j++) {
          if (newObject[subset[j].name]) {
            newObject[subset[j].name]++;
          } else {
            newObject[subset[j].name] = 1;
          }
          sum += subset[j].seat;
      }
      const difference = number - sum;

      newObject.ambulatory = difference;

      if(sum <= number) {
          subsets.add(JSON.stringify(newObject));
      }
  }

  return [...subsets].map(subset => JSON.parse(subset));
};

const a = [{
  name: 'grocery',
  capacity: 2,
  total: 5
}, {
  name: 'wheelchair',
  capacity: 0,
  total: 3
}];
const hrStart = process.hrtime();
const array = [];

for (let i = 0, len = a.length; i < len; i++) {
  for (let tot = 0, len2 = a[i].total; tot < len2; tot++) {
    array.push({
      name: a[i].name,
      seat: a[i].capacity
    });
  }
}
const combinations = subsetsLessThan(array, 10);
const hrEnd = process.hrtime(hrStart);
// for (const combination of combinations) {
//   console.log(combination);
// }

console.info('Execution time (hr): %ds %dms', hrEnd[0], hrEnd[1] / 1000000)

Ожидаемые результаты - это все комбинации результатов, которые были переданы, чтобы быть меньше, чем вместимость транспортного средства, поэтомуПо сути, это комбинация алгоритма меньше суммы.Например, ожидаемый результат кода, который я разместил, будет ->

[{"ambulatory":10},{"wheelchair":1,"ambulatory":10},{"wheelchair":2,"ambulatory":10},{"wheelchair":3,"ambulatory":10},{"grocery":1,"ambulatory":8},{"grocery":1,"wheelchair":1,"ambulatory":8},{"grocery":1,"wheelchair":2,"ambulatory":8},{"grocery":1,"wheelchair":3,"ambulatory":8},{"grocery":2,"ambulatory":6},{"grocery":2,"wheelchair":1,"ambulatory":6},{"grocery":2,"wheelchair":2,"ambulatory":6},{"grocery":2,"wheelchair":3,"ambulatory":6},{"grocery":3,"ambulatory":4},{"grocery":3,"wheelchair":1,"ambulatory":4},{"grocery":3,"wheelchair":2,"ambulatory":4},{"grocery":3,"wheelchair":3,"ambulatory":4},{"grocery":4,"ambulatory":2},{"grocery":4,"wheelchair":1,"ambulatory":2},{"grocery":4,"wheelchair":2,"ambulatory":2},{"grocery":4,"wheelchair":3,"ambulatory":2},{"grocery":5,"ambulatory":0},{"grocery":5,"wheelchair":1,"ambulatory":0},{"grocery":5,"wheelchair":2,"ambulatory":0},{"grocery":5,"wheelchair":3,"ambulatory":0}]

Answer 1

Существует один трюк, который вы можете использовать для улучшения алгоритма, который называется backtracking : если вы достигли невозможного пути, например, 5 -> 6, тогда вам не нужно продолжать поиск там, так как 5 + 6 уже больше 10. Благодаря этому вы можете исключить множество комбинаций.

   function* combineMax([current, ...rest], max, previous = {}) {
     // Base Case:  if there are no items left to place, end the recursion here
     if(!current) { 
       // If the maximum is reached exactly, then this a valid solution, yield it up
       if(!max) yield previous; 
       return;
     }

     // if the "max" left is e.g. 8, then the grocery with "seat" being 2 can only fit in 4 times at max, therefore loop from 0 to 4
     for(let amount = 0; (!current.seat || amount <= max / current.seat) && amount <= current.total; amount++) {
       // The recursive call
       yield* combineMax(
        rest, // exclude the current item as that was  used already
        max - amount * current.seat, // e.g. max was 10, we take "seat: 2" 3 times, then the max left is "10 - 2 * 3"
        { ...previous, [current.name]: amount } // add the current amount
       );
     }
   }

   const result = [...combineMax([
    { name: 'grocery', seat: 2, total: Infinity }, 
    { name: 'wheelchair', seat: 0, total: 3 },
    { name: 'ambulatory equipment', seat: 1, total: Infinity },
     //...
   ], 10)];