Got this task from a game. Farmer has
- a field of constant size 16
- a daily water supply which he can improve while progressing the game. For a given day it is 100, in a few days it may become 130.
- around 50 types of crops. Each crop has daily yield (in gold coins) and water consumption.
Each crop type must be unique (planted once per day)
The goal is to get maximum gold per day.
Which breaks down to finding 1-16 crops whose sum of water consumption is no more than water supply (input parameter, e.g. 100) and yield sum is maximum.
Crop types are generated randomly with yield range 10-50000 and consumption range 1-120.
Brute force needs 50!/(50-16)! iterations - about 10e27.
Are there any more optimal ways to find max output?
CodePudding user response：
This is called the Knapsack problem. Here's pseudocode lifted from Wikipedia.
// 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])