Разделите на n корзин с минимальными затратами

Question

1. Рассмотрим 2*k кортежи (a0, b0), (a1, b1), ... и 2 корзины A и B. Размещение кортежа i-th в корзине A обойдется вам aiдоллар, в корзине B будет стоить bi доллар.Какова минимальная стоимость размещения k элементов в корзине A и k элементов в корзине B.

Я придумал жадный алгоритм: отсортировать массив кортежей, взяв abs(ai - bi) в качестве ключав порядке убывания.Однако можем ли мы решить эту проблему с помощью динамического программирования?Что если есть n корзин вместо двух.

Answer 1

Пусть dp[i][j] - минимальная стоимость, когда элемент j помещается в корзину A для первых элементов i, например, dp[0][0] - минимальная стоимость для помещения 0 элементов в A для первых 0 элементов;dp[4][2] - это минимальная стоимость для помещения 2 элементов в A для первых 4 элементов

Затем: для элемента ith (индекс i - 1, поэтому я использую b[i - 1] и a[i - 1]),нам нужно поместить его в корзину A или B. Таким образом, мы вычисляем минимум двух случаев:

dp function: dp[i][j] = Math.min(dp[i - 1][j] + b[i - 1], dp[i][j - 1] + a[i - 1])

Тогда проблема состоит в том, чтобы получить dp[2*k][k]