Ask a question in Java algorithm to solve the train of thought-CodePudding

Question: is there an A collection of objects, A length is n, each with A value of x, y interest on the properties of the are floating point, now from the collection to choose the number of A, minimum requirements shall not exceed the total amount of k and interest, selected A number of m, could you tell me how to solve in Java?
I try to use backtracking algorithm to solve this problem, the current problems is when n more than 50, calculation time very much, don't know if algorithm have what problem,
Is there anyone who share the solution,

CodePudding user response:

refer to the original poster Gerlias response:

problem: there is A A collection of objects, A length is n, each with A value of x, y interest on the properties of the are floating point, now from the collection to choose the number of A, minimum requirements shall not exceed the total amount of k and interest, selected A number of m, could you tell me how to solve in Java?
I try to use backtracking algorithm to solve this problem, the current problems is when n more than 50, calculation time very much, don't know if algorithm have what problem,
Is there anyone who share the solution,

problem correct once, not A length is n, should be set for the length of the n

CodePudding user response:

You this is like a 0-1 knapsack problems, now can't remember too clear, but I remember at the beginning of this problem is to use dynamic programming to solve, not backtracking, operational research there, you can look at the related information

CodePudding user response:

refer to the second floor King * reply:

you this question is very like 0-1 knapsack problem, now can't remember too clear, but I remember at the beginning of this problem is to use dynamic programming to solve, not backtracking, operational research there, you can go to see the relevant information

considered using dynamic programming, but not out of the equation of state,

CodePudding user response:

After another wall bumps bumps

CodePudding user response:

Conditions for wrong, zero choice is not to go?

CodePudding user response:

reference 5 floor nayi_224 reply:

give wrong condition, zero choice is not to go?

sorry, condition is a less, total amount not less than x

CodePudding user response:

Verified that the problem wasn't the dynamic programming algorithm, already use greedy algorithm to solve,

CodePudding user response:

According to the interest of sorted collection first, and then traverse the judgment amount can be