Этот вопрос мотивирован этим вопросом:
Вариация на рюкзаке - минимальное общее значение, превышающее 'W'
Предположим, что вместо этого у нас есть проблема многомерного ранца:
Учитывая обычные n наборы предметов (скажем, каждый неограниченный) с весами и значениями:
w1, z1, v1
w2, z2, v2
...
wn, zn, vn
и целевой вес W, мне нужно выбрать элементы так, чтобы сумма w была не менее W, сумма z была не более Z и общее значение минимизировано .
Существует ли элегантное решение этой проблемы, например, вопрос, о котором я говорил выше, то есть использовать дополнительную проблему с рюкзаком?