Делитесь фруктами честно (Динамическое программирование)
Мне очень трудно понять, как эффективно решить эту проблему. Позвольте мне описать, как это происходит:
«Трудолюбивая мама купила несколько фруктов с разной питательной ценностью для своих троих детей, Амелии, Джессики и Бруно. У обеих девочек лишний вес, они очень злые и всегда оставляют бедного Бруно ни с чем, поэтому их мать решила разделить еду в следующим образом:
- Амелия, будучи самой тяжелой, получает наибольшее количество Пищевой Ценности
- Джессика получает сумму, равную или меньшую, чем Амелия
- Бруно получает количество, равное или меньшее, чем Джессика, но вам нужно найти способ дать ему максимально возможную пищевую ценность при соблюдении правила (A >= J >= B )"
Примечание. :Исходная проблема описана по-другому, но идея та же. Я не хочу, чтобы мои одноклассники нашли этот пост, когда будут искать помощь в Google, хе-хе.
Один из тестовых случаев, данных моим учителем, следующий:
The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1}
Input:
7 -----> Number of Fruits
4 2 1 8 11 5 1 ----> Fruits Nutritional Values
Output:
1 11 ----> One fruit, their nutritional values sum for Amelia
5 ----> Position of the fruit in the list
3 11 ----> Three fruits, their nutritional values sum for Jessica
1 2 6 ----> Position of the fruits in the list
3 10 ----> Three fruits, their nutritional values sum for Bruno
3 4 7 ----> Position of the fruits in the list
Примечание. :Я знаю, что есть несколько способов нырнуть за фруктами среди детей, но на самом деле это не имеет значения, если следует правилу A >= J >= B.
Сначала я сделал алгоритм, который генерировал все подмножества, у каждого были свои суммы и используемые позиции. От этого метода быстро отказались, потому что список фруктов может содержать до 50 фруктов, а алгоритм подмножества — O (2^n ). У меня закончилась память.
Вторая идея, которая у меня есть, заключается в использовании динамического программирования. В заголовке столбцов у меня были бы позиции списка фруктов, в заголовке строки то же самое, это сложно объяснить буквами, поэтому я заранее сделаю таблицу для предыдущего примера { 4, 2, 1, 8, 11, 5, 1}.
00 01 02 03 04 05 06 07
00
01
02
03
04
05
06
07
Каждый раз, когда мы переходим к строке ниже, мы добавляем позиции 1,2,3,...,7
00 01 02 03 04 05 06 07
00 00 <---No positions in use
01 04 <---RowPosition 1 + Column Position(Column 0) (4+0)
02 06 <---RowPosition 1 + RowPosition 2 + Column Position (4+2+0)
03 07 <---RP(1) + RP(2) + RP(3) + CP(0) (4+2+1+0)
04 15 <--- (4+2+1+8+0)
05 26
06 31
07 32 <--- (4+2+1+8+11+5+1+0)
Теперь, когда вы знаете, как это делается, давайте добавим первую строку
00 01 02 03 04 05 06 07
00 00 04 02 01 08 11 05 01 <-- Sum of RP + CP
01 04 00 06 05 12 15 09 05 <-- Sum of RP(0..1) + CP
02 06
03 07
04 15
05 26
06 31
07 32
Я поставил 00, потому что 1-я позиция уже используется. Готовая таблица будет выглядеть так.
00 01 02 03 04 05 06 07
00 00 04 02 01 08 11 05 01
01 04 00 06 05 12 15 09 05
02 06 00 00 07 14 17 11 07
03 07 00 00 00 15 18 12 08
04 15 00 00 00 00 26 20 16
05 26 00 00 00 00 00 31 27
06 31 00 00 00 00 00 00 32
07 32 00 00 00 00 00 00 00
Теперь, когда у нас есть стол. Я делю сумму Пищевой Ценности на количество детей, 32/3 = 10,6667, максимальное значение будет 11. Я пытаюсь проверить 11, если оно есть в таблице, я выбираю его и отмечаю положение строки и столбцы таблиц, как они используются, тогда я попытался бы снова проверить 11, если он есть в таблице, я выбираю его, в противном случае смотрю на 10 или 9 и т. д., пока не найду его. После этого я помечал соответствующие позиции как использованные, а затем суммировал неиспользованные позиции, чтобы получить плоды Бруно.
Я знаю, что должен быть лучший способ сделать это, потому что я нашел недостаток в своем методе, таблица содержит только сумму нескольких подмножеств. Так что, возможно, это будет вредно в нескольких тестовых случаях. Может быть, 3D Memoization Cube? Я думаю, что это будет потреблять слишком много памяти, и у меня слишком много ограничений 256 МБ.
Вау, я и не думал, что набрал столько x.X. Надеюсь, я не получу много tl; доктор. Мы будем очень признательны за любую помощь / руководство :D
РЕДАКТИРОВАТЬ :Я сделал код, который генерирует таблицу, на случай, если кто-то захочет попробовать.
static void TableGen(int[] Fruits)
{
int n = Fruits.Length + 1;
int[,] memo = new int[n, n];
for (int i = 1; i < n; i++)
{
memo[0, i] = Fruits[i - 1];
memo[i, 0] = memo[i - 1, 0] + Fruits[i - 1];
for (int j = i + 1; j < n; j++)
memo[i, j] = memo[i, 0] + Fruits[j - 1];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
Console.Write("{0:00} ", memo[i, j]);
Console.WriteLine();
}
}