Проблема с рюкзаком - выбор наилучшей комбинации предметов из 5 комплектов, включая 1 предмет из каждого комплекта - PullRequest
Новая
       49

Проблема с рюкзаком - выбор наилучшей комбинации предметов из 5 комплектов, включая 1 предмет из каждого комплекта

1 голос
/ 06 ноября 2019

У меня есть 5 двумерных массивов, содержащих значение элемента и цену элемента, они выглядят так: 

A = [
    [1, 1],
    [2, 5],
    [3, 7],
    ...
]
...
...

E = [
    [4, 15],
    [12, 25],
    [33, 57],
    ...
]

Первый столбец - это элемент value, а второй - price

что яхочу получить окончательный набор из 5 значений, в котором каждый элемент будет из другого начального массива, поэтому конечный результат должен выглядеть, например, как [A[1], B[15], C[46], D[3], E[0]], критерии для выбранных элементов являются своего рода стандартом для задачи рюкзака - лучшее значение для всех элементов, в то время какудерживая сумму цен выбранных элементов (второй столбец) под заданным порогом, например, 500

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

1) предварительно вычислить все возможные результаты для данных параметров и кэшировать их

2) создать соотношение цена / производительность и упорядочить по ним элементы, а затем найти способнайти примерное лучшее решение

1 Ответ

1 голос
/ 06 ноября 2019

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

Пусть dp[i][j] будет лучшим значением с j ценой, уже использованной после выбора элемента из i-го массива. 

for (int i = 0; i <= 5; i++)
  for (int j = 0; j <= 500; j++)
    dp[i][j] = -1;

dp[0][0] = 0;

for (int i = 1; i <= 5; i++) { // From array A to array E
  for (int j = 0; j < size_of_ith_array; j++) {
    for (int p = 0; p <= 500; p++) {
      if (p >= price[i][j] && dp[i - 1][p - price[i][j]] != -1)
        dp[i][p] = max(dp[i - 1][p - price[i][j]] + value[i][j], dp[i][p]);
    }
  }
}

ans = max(dp[5][0 to 500])
...