從游戲中獲得此任務。農民有
- 大小恒定為 16 的欄位
- 每天的供水，他可以在進行游戲的同時改善。某一天是 100，幾天后它可能會變成 130。
- 大約50種作物。每種作物都有每日產量（以金幣計）和耗水量。
每種作物型別必須是唯一的（每天種植一次）
目標是每天獲得最多的金幣。
這分解為找到1-16種作物，其耗水量之和不超過供水量（輸入引數，例如100）并且產量總和最大。
作物型別隨機生成，產量范圍為 10-50000，消耗范圍為 1-120。
蠻力需要 50!/(50-16)! 迭代 - 大約 10e27。
有沒有更好的方法來找到最大輸出？
uj5u.com熱心網友回復：
這稱為背包問題。這是從維基百科中提取的偽代碼。
// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.
array m[0..n, 0..W];
for j from 0 to W do:
m[0, j] := 0
for i from 1 to n do:
m[i, 0] := 0
for i from 1 to n do:
for j from 0 to W do:
if w[i] > j then:
m[i, j] := m[i-1, j]
else:
m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] v[i])
https://en.wikipedia.org/wiki/Knapsack_problem
https://medium.com/@fabianterh/how-to-solve-the-knapsack-problem-with-dynamic-programming-eb88c706d3cf
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/533656.html
標籤：算法排列
下一篇：畫90度角線的演算法