I have a problem with solve my exercise. I read about dynamic programming and algorithms and I think my exercise is "specific knapsack problem". I solved it with brute force method but I can't solve it with dynamic programming.
I have a ship (knapsack) which has 300 tons of weight. There are crystals which have in themselves 3 substances (X, Y, Z) - each other substance has weight and all crystals have the same value. I need to pack to ship as many as possible crystals but the proportions of substances of all packed crystals must be 1:1:1. But for example if I have three crystals with proportions 1:1:1 which give the biggest number of tons and eight crystals which give the same number of tons (two other combinations of crystals give the biggest number of tons) I need to choose the combinations with the lowest number of crystals.
I solved it with brute force method - I created a list of arrays of all combinations. Next I found they combinations with 1:1:1 proportions. Next I found the combination which gives the biggest number of tons and has the lowest number of crystals (if there are two or more combinations with the same biggest number of tons). I checked tests and it returned good scores, I haven't any idea how can I solve it with dynamic programming ;/ Is there someone who help me?
For Example when I have 10 crystals:
1) X =2 Y =3 Z =4
2) X =5 Y=10 Z =2
3) X =3 Y =3 Z =3
4) X =1 Y =0 Z =6
5) X =9 Y=12 Z =4
6) X =1 Y =1 Z =1
7) X =2 Y =1 Z=0
8) X =1 Y =2 Z =3
9) X =1 Y =1 Z =1
10) X =4 Y =3 Z =3
The solution is: max 27 tons with five crystals (numbers: 1, 3, 6, 7 and 9)