Рюкзак (многокритериальный)

Question

Если у меня есть рюкзак, где вес w имеет два значения v1 и v2, а емкость равна m. Как я найду общие значения для v1 и v2, где вес не превышает емкость m?

Answer 1

Итак, ваша проблема определяется следующим образом. Сначала некоторые (определения переменных с примерами значений):

int N = 4; // number of items to choose from
int m = 6; // maximum weight in knapsack

// weight for an item[i] to be summed up, upper limited = m
int weight[N] = {5,2,4,3}; 

// two values for each items:
int values[2][N] = {
  {1,3,5,2},
  {6,3,2,4}
};

Рюкзак должен быть заполнен предметами, не превышающими вес "m" для суммы веса для всех предметов в рюкзаке. Где у вас есть 2 значения для каждого элемента. Мы могли бы рассматривать эту проблему как:

Я хочу поехать в отпуск на самолете со своей девушкой. И у нас есть один чемодан (= рюкзак) и N предметов на выбор. У каждого предмета есть вес, и сумма веса не может быть слишком высокой (например, воздушная линия ограничения веса составляет 25 кг, а чемодан - 1 кг, поэтому у нас в качестве предела для предметов m=24 кг). Для каждого элемента у нас есть 2 значения. Значения [1][N] - это значения для меня (для того, чтобы в нашем туре был предмет n в рюкзаке). Значения [2][N] - это значения для моей подруги, у которой разные предпочтения. Мы также предполагаем, что каждый предмет можно положить только один раз в рюкзак и что общая стоимость рюкзака - это сумма их значений для меня, добавленная к сумме их значений для нее.

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

int value[N] = {(1+6),(3+3),(5+2),(2+4)};

Или просто:

int value[N] = {7, 6, 7, 5};

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

Как оптимально решить обычную проблему с рюкзаком, описано в Википедии. Взгляните на http://en.wikipedia.org/wiki/Knapsack_problem - если английский не ваш родной язык, взгляните также на версию на вашем языке (выберите язык в меню).

Если вам нужна дополнительная помощь, просто спросите.