Рюкзак проблема или перестановка? Как решить мою проблему?

Question

Здравствуйте, надеюсь, кто-нибудь может мне помочь или, по крайней мере, дать мне представление в правильном направлении.

У меня есть массив размером от 100 до 500 элементов. Каждый элемент имеет атрибуты name (строка), вес (float), точки (float), position (int). Максимальный вес не является фиксированным числом, позиции равны (1,2,3,4,5), каждая позиция должна быть заполнена. Каждый предмет может быть использован только один раз. Результатом должно стать 15 комбинаций с максимальным количеством очков 7 пунктов.

Насколько мой ноутбук разбился из-за переполнения памяти.

Я пробовал решение в машинописи для использования Firebase.

import * as functions from "firebase-functions";

// // Start writing Firebase Functions
// // https://firebase.google.com/docs/functions/typescript
//
export const potItems = functions.https.onRequest((request, response) => {
    let possibleItems: any[] = [];
    let counter: number = 0;
    const items = [
        { name: "James Harden", position: "PG", weight: 15.9, points: 62.63 },
        { name: "Russell Westbrook", position: "PG", weight: 14.9, points: 56.12 },
        { name: "LeBron James", position: "SF", weight: 15.9, points: 55.67 },
        { name: "Bradley Beal", position: "SG", weight: 14.8, points: 52.69 },
        { name: "Anthony Davis", position: "PF", weight: 14.6, points: 52.16 },
        { name: "Damian Lillard", position: "PG", weight: 13.5, points: 49.34 },
        { name: "Nikola Vucevic", position: "C", weight: 12.9, points: 47.97 },
        { name: "Domantas Sabonis", position: "PF", weight: 12.8, points: 47.6 },
        { name: "Kristaps Porzingis", position: "PF", weight: 13.5, points: 47.18 },
        { name: "Andre Drummond", position: "C", weight: 12.2, points: 45.97 },
        { name: "Kawhi Leonard", position: "SF", weight: 13.2, points: 46.08 },
        { name: "Hassan Whiteside", position: "C", weight: 12.2, points: 45.83 },
        { name: "DeAndre Ayton", position: "C", weight: 11.8, points: 45.57 },
        { name: "Paul George", position: "SF", weight: 11.1, points: 43.8 },
        { name: "D'Angelo Russell", position: "PG", weight: 11.5, points: 44.0 },
        { name: "Julius Randle", position: "PF", weight: 11.3, points: 42.46 },
        { name: "DeMar DeRozan", position: "SG", weight: 11.2, points: 40.6 },
        { name: "Coby White", position: "PG", weight: 10.5, points: 37.85 },
        { name: "Ricky Rubio", position: "PG", weight: 11.1, points: 37.83 },
        { name: "Robert Covington", position: "SF", weight: 9.1, points: 37.26 },
        { name: "James Harden", position: "PG", weight: 15.9, points: 62.63 },
        { name: "Russell Westbrook", position: "PG", weight: 14.9, points: 56.12 },
        { name: "LeBron James", position: "SF", weight: 15.9, points: 55.67 },
        { name: "Bradley Beal", position: "SG", weight: 14.8, points: 52.69 },
        { name: "Anthony Davis", position: "PF", weight: 14.6, points: 52.16 },
        { name: "Damian Lillard", position: "PG", weight: 13.5, points: 49.34 },
        { name: "Nikola Vucevic", position: "C", weight: 12.9, points: 47.97 },
        { name: "Domantas Sabonis", position: "PF", weight: 12.8, points: 47.6 },
        { name: "Kristaps Porzingis", position: "PF", weight: 13.5, points: 47.18 },
        { name: "Andre Drummond", position: "C", weight: 12.2, points: 45.97 },
        { name: "Kawhi Leonard", position: "SF", weight: 13.2, points: 46.08 },
        { name: "Hassan Whiteside", position: "C", weight: 12.2, points: 45.83 },
        { name: "DeAndre Ayton", position: "C", weight: 11.8, points: 45.57 },
        { name: "Paul George", position: "SF", weight: 11.1, points: 43.8 },
        { name: "D'Angelo Russell", position: "PG", weight: 11.5, points: 44.0 },
        { name: "Julius Randle", position: "PF", weight: 11.3, points: 42.46 },
        { name: "DeMar DeRozan", position: "SG", weight: 11.2, points: 40.6 },
        { name: "Coby White", position: "PG", weight: 10.5, points: 37.85 },
        { name: "Ricky Rubio", position: "PG", weight: 11.1, points: 37.83 },
        { name: "Robert Covington", position: "SF", weight: 9.1, points: 37.26 }
    ];

        for (let index0 = 0; index0 < items.length; index0++) {
          for (let index1 = 0; index1 < items.length; index1++) {
            if (index1 == index0) {
              break;
            }
            for (let index2 = 0; index2 < items.length; index2++) {
              if (index2 == index0 || index2 == index1) {
                break;
              }
              for (let index3 = 0; index3 < items.length; index3++) {
                if (index3 == index0 || index3 == index1 || index3 == index2) {
                  break;
                }
                for (let index4 = 0; index4 < items.length; index4++) {
                  if (
                    index4 == index0 ||
                    index4 == index1 ||
                    index4 == index2 ||
                    index4 == index3
                  ) {
                    break;
                  }
                  for (let index5 = 0; index5 < items.length; index5++) {
                    if (
                      index5 == index0 ||
                      index5 == index1 ||
                      index5 == index2 ||
                      index5 == index3 ||
                      index5 == index4
                    ) {
                      break;
                    }
                    for (let index6 = 0; index6 < items.length; index6++) {
                      if (
                        index6 == index0 ||
                        index6 == index1 ||
                        index6 == index2 ||
                        index6 == index3 ||
                        index6 == index4 ||
                        index6 == index5
                      ) {
                        break;
                      }
                      let item: number[] = [];
                        item.push(index0);
                        item.push(index1);
                        item.push(index2);
                        item.push(index3);
                        item.push(index4);
                        item.push(index5);
                        item.push(index6);
                        item.sort((a, b) => a - b);
                        counter++;
                        possibleItems.push(counter);
                        console.log("item " + counter + ": " + item);

                    }
                  }
                }
              }
            }
          }
        }
        response.send("All items: " + possibleItems);
});

Элементы здесь просто пример того, как они могут выглядеть

спасибо за вашу помощь

Answer 1

Итак, у вас есть 7 позиций для заполнения, чтобы максимизировать сумму очков?

Группируйте свои позиции по позициям, сортируйте каждую группу по точкам.

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

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

Я не знаю, какова ваша мера, чтобы выбрать 15 комбинаций. Если вы только максимизируете их суммарные баллы, вы можете выбрать все, что захотите. Если вы хотите сделать комбинации более равномерными (у каждого есть элементы с меньшим разбросом точек внутри комбинации или меньшим разбросом суммарных баллов среди комбинаций), вы можете добавить больше ограничений.

Я думаю, что-то вроде линейное программирование может быть полезным в этом случае, потому что вы оптимизируете линейную целевую функцию (сумму).