What if there are multiple solutions?
What if there are multiple solutions yielding the same value but different weights?
I'm pretty sure the weight won't matter, but I'd like confirmation all the same...
| |
Re: What if there are multiple solutions?
What if there are multiple solutions yielding the same value but different weights?
I'm pretty sure the weight won't matter, but I'd like confirmation all the same...
As far as I understand, just select one solution; it does not matter what weight it is, as long as it satisfies the criteria. This is how the problem it formulated.
| |
Re: What if there are multiple solutions?
As far as I understand, just select one solution; it does not matter what weight it is, as long as it satisfies the criteria. This is how the problem it formulated.
Thanks mikhailsemenov. You're probably right, but won't hurt to find out for sure from clay...
| |
Re: What if there are multiple solutions?
As far as I understand, just select one solution; it does not matter what weight it is, as long as it satisfies the criteria. This is how the problem it formulated.
Probably it's true but I i think the best solution is the one with higher ratio total_value/ total_weight. With less weight you obtain the same value.
| |
Re: What if there are multiple solutions?
Probably it's true but I i think the best solution is the one with higher ratio total_value/ total_weight. With less weight you obtain the same value.
The problem statement asks for the optimal solution, so that means you want to find the solution that fills the knapsack the most and gives the highest value.
The first solution is picking one item that has weight < max_weight and stating that X of that item is all that is needed. That is not an optimal solution, but it could be the first solution that your algorithm encounters.
You need to find all possible fill solutions and pick the one that is the closest to the knapsack capacity (by weight).
====================================================
| Need a Job? http://www.accessquery.com |
====================================================
| Need a plan? http://www.extremeplannerlive.com |
====================================================
If you think it\'s expensive to hire a professional to
do the job, wait until you hire an amateur.
| |
Re: What if there are multiple solutions?
What if there are multiple solutions yielding the same value but different weights?
I'm pretty sure the weight won't matter, but I'd like confirmation all the same...
Is it still possible to fit another item in? In my opinion, I would consider that a bug and set off to fix it.
| |
Re: What if there are multiple solutions?
Is it still possible to fit another item in? In my opinion, I would consider that a bug and set off to fix it.
Let me clarify with an example:
4.2 4 2
abc 4.1 10
def 1 2.5
Clearly, there are two solutions:
1 * abc -> value = 10, weight = 4.1
4 * def -> value = 10, weight = 4.0
| |
Re: What if there are multiple solutions?
The problem statement asks for the optimal solution, so that means you want to find the solution that fills the knapsack the most and gives the highest value.
The first solution is picking one item that has weight < max_weight and stating that X of that item is all that is needed. That is not an optimal solution, but it could be the first solution that your algorithm encounters.
You need to find all possible fill solutions and pick the one that is the closest to the knapsack capacity (by weight).
By that definioion, I could just pick one instance of the first object that fits within the specified max_weight and claim that as my solution. So, no, that's not how I would go about finding a solution...
The first solution, for me, would be the one where weight == max_weight. If such an instance is not present at all, then, I would go through all possible solutions, and pick the one with maximum value.
| |
Re: What if there are multiple solutions?
Let me clarify with an example:
4.2 4 2
abc 4.1 10
def 1 2.5
Clearly, there are two solutions:
1 * abc -> value = 10, weight = 4.1
4 * def -> value = 10, weight = 4.0
First off, the judges would try to devise a data set that avoids this problem. But, it's still an interesting possibility (and might take very careful planning to avoid), so we'll address it.
The problem statement asks code entries to find the (optimal) solution "that maximizes the total value yet still fits within a weight restriction." Both of the two solutions given above satisfy the criteria with their equal values. Thus, the judges would accept either of the solutions as being "optimal".
If the threaded code devised several potential solutions (all of which meet the weight requirement), the final determination to pick one of these several options would be to pick one, test all the others against that current chosen solution, and replace it if the new solution's value was (strictly) greater than the current. If the two options above were compared, whichever one was the "current" solution would remain the current solution since the new possibility does not have a greater value.
One might argue that the lighter weight solution would be the "optimal" since it would be easier to carry. Another might think (as was pointed out in a post in this thread) that putting the most weight for the same value is optimal. Since both arguments have merit, either of the solutions would be accepted. [This latter view would easily apply to consumables. The judges would rather carry a 4.1 pound bar of chocolate than 4.0 pounds of text books. Such a distinction is beyond the scope of the problem.]
--clay
| |
Re: What if there are multiple solutions?
First off, the judges would try to devise a data set that avoids this problem.
Wait, I'm confused, you create the data-set?
| | |
