Эффективное распределение крафтовых ресурсов - PullRequest
0 голосов
/ 13 марта 2020

Я работаю над игрой, в которой вы создаете различные предметы. Ресурсы ограничены, и мне нужно рассчитать максимальное количество раз, которое может быть сделан каждый элемент, исходя из того, что доступно. У меня все работает, кроме последней части алгоритма.

Во-первых, давайте представим, что мы рассчитываем максимальное количество моркови, которое мы можем вырастить. В рецепте есть несколько шагов, чтобы вырастить 1 морковь:

Морковь: потреблять 1 воду, использовать 1 участок фермы

Вода: использовать 1 ведро, использовать 1 пруд

Ведро: Потребление 7 Древесина

Участок фермы: Потребление 2 Древесина, Потребление 1 Почва

Почва: Используйте 1 лопату, Используйте 1 Яму для грязи

Совок: Потребляйте 2 Древесины

Если это не ясно: для выращивания моркови мы добавляем ведро воды на участок фермы. Для сбора воды мы используем ведро на пруду. Каждое ведро сделано из 7 кусков дерева. Каждый фермерский участок состоит из двух кусков дерева и 1 почвы… и др c. Если мы «потребляем» предмет, все его использование немедленно истощается. Однако, если предмет «используется», он теряет только 1 использование во время производства. Например, участок фермы может быть использован 4 раза для выращивания моркови перед уничтожением. Допустим, предметы имеют следующее использование:

Морковь: 1 использование

Вода: 1 использование

Ведро: 15 использований

Участок фермы : 4 использования

Почва: 1 использование

Лопата: 20 использований

Дерево: 1 использование

Итак, вот где я застрял : обратите внимание, что для нескольких частей рецепта требуется дерево. Для простоты давайте представим, что мы можем взять 100 кусков дерева. Мне нужен способ подсчитать, сколько дерева должно быть выделено на каждую часть рецепта. В настоящее время я делаю это так: (woodUsesInStep / totalWoodUses) * amountOfWood. Итак, если мы посмотрим, сколько древесины получит ведро, оно будет: (7/11) * 100 = ~ 64 кусков дерева. Проблема в том, что это не даст наибольшего количества моркови….

Используя этот алгоритм, я получаю следующие результаты:

Ведро: выделено 64 дерева, сделано 9 ведер

Лопата: выделено 18 дров, изготовлено 9 лопат

Земельный участок: выделено 18 дров, создано 9 фермерских участков

Окончательный результат: 36 морковей можно сделать

Но вот результаты, которые я хочу:

Ведро: 49 деревянных, 7 изготовленных ведер

Лопата: 4 деревянных, 2 изготовленных лопаты

Сельскохозяйственный участок : 46 дерева, 23 фермерских участка

Окончательный результат: можно сделать 92 моркови

Каким-то образом мне нужно определить, какая часть рецепта дает более высокие результаты, и выделить древесину на основе на этом, но я в настоящее время нахожусь в тупике о том, как go об этом.

1 Ответ

1 голос
/ 13 марта 2020

Как вы уже обнаружили, ваша текущая формула использует стоимость каждого ресурса («ингредиента») в рецепте, чтобы вычислить, как сделать равное количество каждого ингредиента. (Вы можете сделать 9 ведер, 9 лопат и 9 фермерских участков с общим количеством древесины 100.) Он не учитывает стоимость каждого ингредиента, а именно: (1) сколько каждого ингредиента требуется по рецепту и ( 2) сколько раз ингредиент можно использовать перед употреблением.

Вы уже определили это вручную и, вероятно, выполнили шаги, аналогичные приведенным ниже. Вы уже знаете, что три ингредиента, которые потребляют древесину, это ведро, лопата и ферма. Чтобы определить, как они должны быть взвешены в вашей формуле, вам нужно определить, сколько каждого ингредиента потребляется для каждой моркови. Вам придется делать это рекурсивно, поскольку некоторые ингредиенты создаются с использованием других ингредиентов.

Когда вы рассчитываете, сколько нужно, помните, что некоторые ингредиенты можно использовать несколько раз, поэтому вы можете не потреблять весь ингредиент. Например, если вам нужна 1 корзина, но в корзине 15 применений, вы фактически потребляете 1/15 корзины. Если эта фракция сбивает с толку, рассмотрим 100 морковь. Если вам нужно использовать ведро 100 раз на 100 морковок, и ведро можно использовать 15 раз перед его потреблением (тогда вам нужно построить лучшие ведра!), Вам нужно 100/15 ведер или 6 2/3 ведра. Это то же самое, что сказать, что каждая морковь потребляет 1/15 ведра, так как 1/15 * 100 = 6 2 / 3.

1 Carrot requires:
1 Water/1 use = 1 Water
1 Farm Plot/4 uses = 1/4 Farm Plot

*** First recursion ***

1 Water requires:
1 Bucket/15 uses = 1/15 Bucket
1 Pond (not applicable to this calculation)

1 Farm Plot requires:
2 Wood/1 use = 2 Wood
1 Soil/1 use = 1 Soil

*** Second recursion ***

1 Bucket requires:
7 Wood/1 use = 7 Wood

1 Soil requires:
1 Shovel/20 uses = 1/20 Shovel
1 Dirt Pit (not applicable to this calculation)

*** Unwinding the recursion ***

*** First recursion ***

1 Water requires:
1/15 Bucket

1 Farm Plot requires:
2 Wood
1 Soil -> 1/20 Shovel

*** Initial ***

1 Carrot requires:
1 Water -> 1/15 Bucket
1/4 Farm Plot -> 1 Farm Plot = {2 Wood + 1/20 Shovel} -> 1/4 * (2 Wood + 1/20 Shovel ) -> 1/2 Wood + 1/80 Shovel

Итак, 1 морковь требует:

1/15 Bucket (1 Bucket = 7 Wood, so 1/15 Bucket = 7/15 Wood)
1/4 Farm Plot (1 Farm Plot = 2 Wood, so 1/4 Farm Plot = 2/4 or 1/2 Wood)
1/80 Shovel (1 Shovel = 2 Wood, so 1/80 Shovel = 1/40 Wood)

Теперь давайте go вернемся к вашей исходной формуле, то есть woodUsesInStep / totalWoodUses * amountOfWood. Для Bucket вы использовали значения 7 для woodUsesInStep и 11 для totalWoodUses, но теперь вы можете видеть, что woodUsesInStep на самом деле 7/15 для Bucket, 1/2 для графика фермы и 1/40 для Shovel, Это означает, что totalWoodUses равно 119/120 (7/15 + 1/2 + 1/40).

Теперь мы можем применить формулу:

Bucket: (7/15) / (119/120) * 100 = 47.1 Wood (makes 6.7 Buckets)
Farm Plot: (1/2) / (119/120) * 100 = 50.4 Wood (makes 25.2 Farm Plots *assuming you have enough Shovels!*)
Shovel: (1/40) / (119/120) * 100 = 2.5 Wood (makes 1.25 Shovels)

Как вы можете видеть при сравнении это к вашим ожидаемым результатам, это довольно близко. На самом деле это дает вам правильное распределение древесины в рецепте, но, к сожалению, это только первая половина проблемы. Так как вы не можете потратить 2,5 дерева или сделать 1,25 лопаты, вам нужен способ определить, округлять ли вверх для каждого ингредиента. У меня нет точной формулы для этой части, но я верю, что это очень приблизит вас:

  1. Начните с ингредиента, из которого вы сделаете меньше всего. (В данном случае это лопата).
  2. Округлите до ближайшего целого числа ингредиентов и вычтите стоимость из ваших общих доступных ресурсов. (В этом случае вы округляете от 1,25 до 2 целых лопат и вычитаете стоимость 4 дров из общего количества 100, оставляя 96 доступных.
  3. Повторяйте эти шаги для каждого ингредиента, пока у вас не закончатся ресурсы:
  4. Следующим ингредиентом является Ведро, так как вы хотите сделать 6,7 из них против 25,2 Земельных участков.
  5. Округлите до 7 Ведер и вычтите стоимость 49 Древесины из оставшихся 96 Древесины, оставив 47 доступных.
  6. Следующим (и последним) ингредиентом является участок фермы. Вы хотели бы округлить 25,2 до 26, но у вас достаточно ресурсов только для 23, так что сделайте их.

Результаты:

2 Shovels
7 Buckets
23 Farm Plots
92 Carrots, as expected

Успех!

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...