CODEWITHSUNDEEP
algorithmpermutation
user1600440
user1600440

Reputation: 53

Algorithm to find permutation with best criteria

Got this task from a game. Farmer has

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?

Upvotes: 1

Views: 101

Answers (1)

Dave
Dave

Reputation: 9085

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])

https://en.wikipedia.org/wiki/Knapsack_problem

https://medium.com/@fabianterh/how-to-solve-the-knapsack-problem-with-dynamic-programming-eb88c706d3cf

Upvotes: 2

Related Questions