Как найти наименьшую сумму чисел для соответствующих элементов, равную заданному значению?

Question

У меня есть следующий ввод

c1, c2
1,  41
2,  76
3,  109
4,  133
5,  149
6,  157
7,  174
8,  185
9,  200
10,  211
11,  223
12,  232
13,  245
14,  258

Что мне нужно сделать, это найти наименьшую сумму c2, для которой сумма соответствующих значений из c1 равна 24.Например, для 10 и 14 сумма равна 469.Я полагаю, это что-то простое для опытного пользователя Excel, которым я точно не являюсь.Значения могут использоваться более одного раза, поэтому 3*8 работает так же хорошо, как и 3*7+3.

Answer 1

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

В любом случае, если значения c1 достаточно просты, скажем, целые числа (без дробей или действительных чисел), вы можете использовать метод динамического программирования, то есть решить множество подзадач, похожих на ваш вопрос, но для суммы ниже 24 и для менее строки то что есть. Объединение их вместе может помочь вам решить сложный вопрос.

Позволяет определить SubProb (N, i) = решение для суммы N в c1, используя только строки 1 ... i. Если это так, SubProb (N, i) = min (взятие экземпляра из i-й строки, без взятия какого-либо экземпляра из i-й строки). Тезисы все варианты доступны. в этом случае это минимум двух простых задач:

• Взяв экземпляр из i-й строки, это означает, что теперь вам нужно взять только Ni больше из c1 и все еще может использовать только 1 ... i строк, так что это значение SubProb (Ni, i), + c2 я.
• Не брать ни одного экземпляра в i-й строке, то есть вы можете просто взять результат SubProb (N, i-1).

Теперь мы вычислим все эти задачи вплоть до SubProb (24,14) в умном порядке и получим желаемый ответ. Самый простой способ сделать это - поместить их в таблицу с осью N, так что легко получить значения без большого количества рекурсивных накладных расходов.

Я реализовал это для вас в файле Excel, вот ссылка. Если вы хотите сделать это при большем значении i или N, просто растяните таблицу, перетащив последнюю строку и ее столбец инструментом расширения (крошечный черный крестик в углу ячейки). Его можно найти по этой ссылке: https://drive.google.com/open?id=1K0iROL9mb2NURM7Q0oUKzAFH4jNxNGtk

Да, и ответ 464.