http://www.spoj.com/problems/SCUBADIV/
We can call this task a "Knapsack probelm with 3 parameters". For solving this we will need a knowledge of "knapsack problem with 2 parameters".
We use a linear array in "knapsack with 2 parameters" where A[I] shows the maxmum value we can get which has a mass of I. In our case we will keep a matrix where A[I][J] shows the minimum mass of cylinders which have I oxygen and J nytrogen. Have a look at the constraints the limits of oxygen and nytrogen are not high which means that keeping a matrix and looping over it won't be much of a problem. Check the source code for a better understanding.
We can call this task a "Knapsack probelm with 3 parameters". For solving this we will need a knowledge of "knapsack problem with 2 parameters".
We use a linear array in "knapsack with 2 parameters" where A[I] shows the maxmum value we can get which has a mass of I. In our case we will keep a matrix where A[I][J] shows the minimum mass of cylinders which have I oxygen and J nytrogen. Have a look at the constraints the limits of oxygen and nytrogen are not high which means that keeping a matrix and looping over it won't be much of a problem. Check the source code for a better understanding.
No comments:
Post a Comment