Риск ранца с надлежащим ограничением отношения и ограничением веса

Question

Задача: Вы производитель соков, который ищет лучших поставщиков для вашего бизнеса. Поставщики продают концентраты, которые содержат 3 ингредиента: X: Y: Z в разных пропорциях. Ваш сок должен иметь эти пропорции как 1: 1: 1, иначе это не будет вкусно. Вес концентрата представляет собой сумму его ингредиентов в фунтах, и все поставщики продают свои концентраты по той же цене, однако ваш грузовик может перевозить до 400 фунтов концентратов. Найти лучших поставщиков для вашего бизнеса: купить (найти) столько фунтов концентрата, сколько сможете (но менее 400 фунтов), зная, что соотношение ингредиентов, отличных от 1: 1: 1, не будет приемлемым.

Вход: Первая строка показывает, сколько концентраты продаются на рынке (менее 200) Следующие п линии о пропорциях X: Y: Z ингредиенты концентратов (в фунтах)

Выход: Первая строка должна быть суммой веса ингредиентов концентратов, которые вы будете покупать (меньше 400 фунтов). Вторая строка должна указать, сколько концентратов вы должны купить, чтобы получить эту сумму, надлежащие пропорции

Пример:

in: 
4 //how many concentrates are sold on the market 
1 2 3 //first concentrate contains 1lb of X, 2lbs of Y, 3 lbs of Z 
0 4 1 
1 3 4 
1 1 1 
2 1 0 

out: 
12 //4lbs of ingredient X + 4lbs Y + 4lbs Z 
3 //we're buying three concentrates: the first one, fourth and fifth (1 2 3; 1 1 1; 2 1 0) so we're getting the biggest amount of it with 1:1:1 ratio of ingredients 

Мое решение: Мое решение было метод грубой силы, которая очень медленно, когда есть много поставщиков, как его сложности 2^(п-2) - этот алгоритм будет просто создать все возможные комбинации концентратов мы могли бы купить, и он будет проверять, являются ли их пропорции 1: 1: 1, если да, то это будет сравнивать их и найти тот, у которого наибольшее количество общих ингредиентов составляет менее 400 фунтов.

Я ищу алгоритм динамического подхода, однако я понятия не имею, как это сделать с надлежащим ограничением отношения.

Answer 1

400/3 = 133 Это означает, что ответ может иметь не более 133 фунтов любого ингредиента. Таким образом, массив DP равен array[134][134][134], где каждая запись в массиве представляет собой количество концентратов для покупки для достижения этой комбинации.

В этом массиве содержится около 2,4 миллиона записей, и массив необходимо сканировать один раз для каждого входа (менее 200). Таким образом, вы просматриваете около 500 миллионов операций для заполнения массива. Это разумно на современном компьютере.

После того, как массив заполнен, простое сканирование находит ответ

for (i = 133; i > 0; i--) 
    if (array[i][i][i] > 0) 
     the answer is array[i][i][i] 

Answer 2

Вот метод, который мог бы позволить нам более низкую эксплуатационную сложность, чем отличная идея user3386109 в. Проводите подсчет сумм отдельно для каждого члена тройки и проследите соответствие (индекс, мощность) для комбинаций по трем перечислениям: для каждого члена троек x, y и z в (x,y,z) итерации по отдельному одномерному массив, представляющие суммы до 133, индексирования мощности:

# for example, Xs enumeration only 
for index, (x,y,z) in triples: 
    for s in [133 - x ... 0] 
    if sums_x[s].cardinalities.length > 0: 
     for cardinality in sums_x[s].cardinalities: 
     sums_x[s + x].by_index.add((index,cardinality + 1)) # this is a set of (index,cardinality) tuples 
     sums_x[s + x].cardinalities["cardinality + 1"].push(index) # hash cardinality to indexes 

    sums_x[x].by_index.add((index,1)) 
    sums_x[x].cardinalities["1"].push(index) 

После того, как мы итерация над три одномерными массивами, один для каждого члена троек, мы можем проследить возможные совпадения. Они делаются редкими из-за низкой вероятности отслеживания согласованного соответствия (суммы, мощности, индекса) по всем трем перечислениям.

Например:

(1 2 3),(0 4 1),(1 3 4),(1 1 1),(2 1 0) 

index = 0 
sums_x[1].by_index = {(0,1)} # (index,cardinality) 
sums_x[1].cardinalities = {"1": [0]} # cardinality: indexes 

index = 1 
sums_x[0].by_index = {(1,1)} # (index,cardinality) 
sums_x[0].cardinalities = {"0,1": [1]} # cardinality: indexes 
sums_x[1].by_index = {(0,1), (1,2)} 
sums_x[1].cardinalities = {"1": [0], "2": [1]} 

... 

index = 4 
sums_x[4].by_index = {(4,3), (4,4)} # (index,cardinality) 
sums_x[4].cardinalities = {"2": [3], "3": [4], "4": [4]} # cardinality: indexes 

sums_y[4].by_index = {(1,1), (3,2), (4,2), (4,3)} 
sums_y[4].cardinalities = {"1": [1], "2": [3,4], "3": [4]} 

sums_z[4].by_index = {(1,2), (2,1), (3,2), (4,3), (4,2)} 
sums_z[4].cardinalities = {"2": [1,3,4], "1": [2], "3": [4]} 

Как мы видим, на сумму 4 в этом примере, есть только один матч (индекс, мощности) во всех трех структур суммы (4,3), которые мы затем можем отслеживать с использованием соответствующих значений:

sums_z[4]: 4,3 
    => val 0 => lookup by z sum (4 - 0) and cardinality (3 - 1) 
    => sums_z[4].cardinalities[2] yields only one match across: index 3 
    => lookup by z sum (4 - 1) and cardinality (2 - 1) 
    => sums_z[3].cardinalities[1] yields a match across: index 0 
    => possible solution, indexes [4,3,0]