If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Anonymous
-
2007-09-24
>> Can i tried using the knapsack dynamic solution to solve it?
This last question reveals that you probably already know more about it than the audience you are asking. This forum is primarily for discussion of Dev-C++ and C/C++ in general, rather than applied mathematics. If you have any problems actually implementing an algorithm in C++ ask away, but selection of any particular algorithm is down to you. I had too look it up, but yes this is a form of Knapsack problem, so one would imagine that the "dynamic solution" applies. Wikipedia discusses the dynamic solution (which I did not immediately understand), and the "Greedy Approximation" algorithm, (which I did). Improvements and variations on the latter are easy to come up with.
If I had no knowledge of existing solutions I might naively suggest the following variation of the 'greedy approximation' suggested in Wikipedia:
1) Sort the table in decreasing order of value.
2) Set current total to zero.
3) Set current table index to zero (largest value)
4) If total plus value at current index is <= the target value and has a repeat count > 0. Decrement the repetition count for that value and add the value to the current total.
5) If total plus value at current index is > target value, or the repeat count at the current index is zero, increment index.
6) Repeat from (4) until index == number of table entries, or total == target.
This is definitely sub-optimal; whether it is acceptable depends upon the purpose of the home work - i.e. is it merely a programming exercise or is it the algorithm itself that is important? If you have been taught the Knapsack Problem as part of this class, then I suggest that you should apply what you have been taught. If the class is a C++ programming class, I would suggest that it does not much matter how you do it so long as you demonstrate appropriate C++ skills.
Clifford
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Okay... Thanks for your suggestion. However if using greedy algorithm defeat the purpose of security and robustness to select the values from a certain group always.
This home work concentrate on a good algorithm and follow by a testing prototype on C++.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Anonymous
-
2007-09-24
I am not sure what your "security and robustness" point is. Unless you test exhaustively it is likly that an algorithm will me sub-optimal - some are worse that others. Selection would depend not only on quality of the answer but also the the taken to produce an answer. You have provided no information upon which to select. Often the 'best' algorithm is not always necessary - 'good enough' is exactly that.
If you already know the "knapsack dynamic solution" use that. I am not really sure what you are asking.
Note that my suggestion also failed to take account of the fact that the solution must use a specific number of values.
If I were just playing with it for fun I might simply take am n-value set selected from the pool at random, and then take the deviation from the target and for each value in the set find another value in the pool for which the difference between the two values is less than the deviation from the target, and swap the values. If you do this iteratively until you either get arbitrarily close, stop getting closer, get to the target, or reach some time limit. You will have to modify this slightly if the aim is not to exceed teh target rather than get as close as possible to it
I am no mathematician, and have no idea is this solution has any mathematical merit, but it would be interesting to try it.
Anyway, I seem to be doing all the work here - what have you done in the meantime?
Clifford
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
As Clifford has stated, this forum is probably not the best place to ask questions
about what the best algorithm to do your homework is. It is not really within the
domain knowledge of most of the regulars here.
(As an aside to the reader - if you find yourself about to ask a question of the form
"Has anyone here ever used XYZ", then, before actually ask this question, search the
forum and see whether XYZ has been previously discussed. If it has not, then the
chances are slim that you are going to get an expert answer. This does not mean that
you might not get help, but you are going to have to ask your question with a good
deal of background information and be a strong partner in solving the problem)
Once you have selected an algorithm, and can provide people here with a clear
description of the algorithm (just posting a name is NOT a clear description),
then you can probably get some hints. Again, you will need to be a strong partner
in doing this, throwing out a very open, unclear scope question that seems to
invite someone to go off and write your code for you will not get it.
Wayne
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Anonymous
-
2007-09-24
OK just for fun I implemented an algorithm based more-or-less based on my earlier suggestion (debugged - it is not a perfect description of what I actually ended up with), and made it repeat the algorithm with a different random initial selection until the deviation was zero; each time printing the solution if better that the previous one - so it converges on an answer. Obviously it may continue indefinitely - this is where a time limit comes in handy.
The output using your data, target value, and a selection of 10 values, with the time taken to produce each selection are shown below:
The random number generator seed was not set so in theory you should be be able to reproduce these exact results. Note that the last four results give exactly 3.29, but because of the inexact representation of decimal floating point values, the calculate deviation is not exactly zero. One way around this is to have a very small minimum acceptable deviation. The algorithm is by no means deterministic, because of the random initialisers, and because that is no guarantee that there ever is a solution.
Now I could post the code, but this is not my homework, and so far you have shown little effort. Make a start on this or your own solution and ask for more specific help where necessary.
Clifford
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Clifford, all your proposed solutions have eleven values.
Anyway, if the values can be negative you'll need to be careful to handle the selection process very carefully--the traditional knapsack approach would fail.
Soma
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Anonymous
-
2007-09-25
>> Clifford, all your proposed solutions have eleven values.
Oh yea... so they do!?
Actually that is an issue with the output display rather than the algorithm. The first value is repeated twice. To get the '+''s in the right place I had intended to print the first, then loop printing "+ n". I forgot to modify the loop to start from 1 rather than zero.
"Dumbass-of-the-day" award to me then!
Clifford
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I didn't say there was anything wrong with your algorithm (As I understood it, your proposition is a simplification of one possible implementation of the all-or-nothing algorithm used in the knapsack problem.), but the description of your proposed algorithm could use a little work.
"I forgot to modify the loop to start from 1 rather than zero."
I would have been willing to bet that that was the case.
""Dumbass-of-the-day" award to me then!"
Possibly. With the original preprocessing--no need in starting the algorithm with all that useless data--I envisioned, adding a single negative to the input data would cause all results produced, if any, to be off by (the required number of values)*(the smallest negative number).
Soma
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Anonymous
-
2007-09-25
Don't be thinking that my code bares a precise resemblance to the description I gave. The description came off the top of my head as I wrote it. I used it as a starting point and fixed and debugged it as it developed. The OP should perhaps do the same, after all that is a normal part of teh development process.
That said I have not given much thought to how it performs with negative values. I am guessing that the actual implementation works whereas the description does not (not in a position to test it at present).
I am of course reluctant to post the code or elaborate on the algorithm until we see some work from the OP - When do you think his deadline is!?
Clifford
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Indeed... which is probably why all the metrics used by management to diagnose a programming project fail to determine anything approaching truth.
"That said I [...] at present)."
I imagine that your implementation, as well as some interpretations of your described algorithm, would work fine for negatives. It all depends on how your 'if' is written. ^_^
It was my, and possibly the OPs assuming he did more than just Google, interpretation of the classic knapsack problem algorithm that has a problem with assuming a positive "weight". (The negative problem inherent in the first draft of my preprocessor is a different issue.)
"I am of course [...] from the OP"
No, you shouldn't do his homework for him (, and neither should anyone else.), but a casual discussion of the merits of our own implementations isn't likely to be detailed enough for the OP to bypass researching an implementation on his own.
"When do you think his deadline is!?"
Knowing the average student... yesterday.
Soma
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
I am supposed to come up with an algorithm and implement in C++.
Question given (in simplified version):
i have a list of double values
Value No. of times repeat
0.0261 61
0.0329 8
0.0414 9
0.0521 6
0.0656 14
0.0826 14
0.104 2
0.131 3
0.1649 11
0.2076 3
0.2613 2
0.329 2
0.4142 2
0.5214 "
0.6564 "
0.8264 "
1.0404 "
1.3098 "
1.6489 "
2.0759 5
2.6134 "
3.29 "
4.1419 "
5.2144 "
6.5645 "
8.2642 "
10.404 1
Suppose i am asked to find 10 values that add up to 3.29 ( it can be any values like 100 values that add up to 3.29 etc)
How am i suppose to go about doing?
Can i tried using the knapsack dynamic solution to solve it?
For the record:
0ms: 0.0261 + 0.0261 + 0.0261 + 0.0261 + 1.6489 + 0.2076 + 0.0414 + 0.2076 + 1.0404 + 0.0414 = 3.2917
15ms: 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 2.6134 + 0.1649 + 0.329 = 3.29
31ms: 0.0329 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.6564 + 0.6564 + 0.1649 + 1.6489 = 3.29
46ms: 0.0329 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 1.6489 + 0.6564 + 0.1649 + 0.6564 = 3.29
437ms: 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 1.6489 + 0.6564 + 0.6564 + 0.1649 + 0.0329 = 3.29
And I randomly changed some of the values to negatives:
0ms: -5.2144 + 0.0329 + -1.0404 + 0.5214 + 10.404 + -0.2613 + 0.0521 + -0.2076 + -1.0404 + 0.0414 = 3.2877
0ms: -4.1419 + -0.329 + 0.0261 + -0.2613 + 0.0656 + 0.5214 + -1.3098 + 0.0414 + 8.2642 + 0.4142 = 3.2909
0ms: -5.2144 + -5.2144 + -4.1419 + 0.4142 + -1.6489 + 0.6564 + 8.2642 + 0.0329 + 10.404 + -0.2613 = 3.2908
15ms: -5.2144 + -1.6489 + -1.3098 + 0.104 + 0.0329 + 2.0759 + 10.404 + 0.0521 + 0.104 + -1.3098 = 3.29
15ms: 2.0759 + 0.6564 + 0.6564 + 0.6564 + 0.6564 + 2.0759 + 0.6564 + 0.6564 + -5.2144 + 0.4142 = 3.29
46ms: 0.5214 + 0.5214 + 0.5214 + 3.29 + 0.0261 + 0.0521 + -0.2076 + 0.0826 + -1.3098 + -0.2076 = 3.29
That's enough 'fun' for now! ;-)
Clifford
>> Can i tried using the knapsack dynamic solution to solve it?
This last question reveals that you probably already know more about it than the audience you are asking. This forum is primarily for discussion of Dev-C++ and C/C++ in general, rather than applied mathematics. If you have any problems actually implementing an algorithm in C++ ask away, but selection of any particular algorithm is down to you. I had too look it up, but yes this is a form of Knapsack problem, so one would imagine that the "dynamic solution" applies. Wikipedia discusses the dynamic solution (which I did not immediately understand), and the "Greedy Approximation" algorithm, (which I did). Improvements and variations on the latter are easy to come up with.
If I had no knowledge of existing solutions I might naively suggest the following variation of the 'greedy approximation' suggested in Wikipedia:
1) Sort the table in decreasing order of value.
2) Set current total to zero.
3) Set current table index to zero (largest value)
4) If total plus value at current index is <= the target value and has a repeat count > 0. Decrement the repetition count for that value and add the value to the current total.
5) If total plus value at current index is > target value, or the repeat count at the current index is zero, increment index.
6) Repeat from (4) until index == number of table entries, or total == target.
This is definitely sub-optimal; whether it is acceptable depends upon the purpose of the home work - i.e. is it merely a programming exercise or is it the algorithm itself that is important? If you have been taught the Knapsack Problem as part of this class, then I suggest that you should apply what you have been taught. If the class is a C++ programming class, I would suggest that it does not much matter how you do it so long as you demonstrate appropriate C++ skills.
Clifford
Okay... Thanks for your suggestion. However if using greedy algorithm defeat the purpose of security and robustness to select the values from a certain group always.
This home work concentrate on a good algorithm and follow by a testing prototype on C++.
I am not sure what your "security and robustness" point is. Unless you test exhaustively it is likly that an algorithm will me sub-optimal - some are worse that others. Selection would depend not only on quality of the answer but also the the taken to produce an answer. You have provided no information upon which to select. Often the 'best' algorithm is not always necessary - 'good enough' is exactly that.
If you already know the "knapsack dynamic solution" use that. I am not really sure what you are asking.
Note that my suggestion also failed to take account of the fact that the solution must use a specific number of values.
If I were just playing with it for fun I might simply take am n-value set selected from the pool at random, and then take the deviation from the target and for each value in the set find another value in the pool for which the difference between the two values is less than the deviation from the target, and swap the values. If you do this iteratively until you either get arbitrarily close, stop getting closer, get to the target, or reach some time limit. You will have to modify this slightly if the aim is not to exceed teh target rather than get as close as possible to it
I am no mathematician, and have no idea is this solution has any mathematical merit, but it would be interesting to try it.
Anyway, I seem to be doing all the work here - what have you done in the meantime?
Clifford
As Clifford has stated, this forum is probably not the best place to ask questions
about what the best algorithm to do your homework is. It is not really within the
domain knowledge of most of the regulars here.
(As an aside to the reader - if you find yourself about to ask a question of the form
"Has anyone here ever used XYZ", then, before actually ask this question, search the
forum and see whether XYZ has been previously discussed. If it has not, then the
chances are slim that you are going to get an expert answer. This does not mean that
you might not get help, but you are going to have to ask your question with a good
deal of background information and be a strong partner in solving the problem)
Once you have selected an algorithm, and can provide people here with a clear
description of the algorithm (just posting a name is NOT a clear description),
then you can probably get some hints. Again, you will need to be a strong partner
in doing this, throwing out a very open, unclear scope question that seems to
invite someone to go off and write your code for you will not get it.
Wayne
OK just for fun I implemented an algorithm based more-or-less based on my earlier suggestion (debugged - it is not a perfect description of what I actually ended up with), and made it repeat the algorithm with a different random initial selection until the deviation was zero; each time printing the solution if better that the previous one - so it converges on an answer. Obviously it may continue indefinitely - this is where a time limit comes in handy.
The output using your data, target value, and a selection of 10 values, with the time taken to produce each selection are shown below:
0ms: 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 1.6489 + 0.2076 + 0.0414 + 0.2076 + 1.0404 + 0.0414 = 3.2917
0ms: 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 2.6134 + 0.1649 + 0.329 = 3.29
15ms: 0.0329 + 0.0329 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.6564 + 0.6564 + 0.1649 + 1.6489 = 3.29
15ms: 0.0329 + 0.0329 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 1.6489 + 0.6564 + 0.1649 + 0.6564 = 3.29
343ms: 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 0.0261 + 1.6489 + 0.6564 + 0.6564 + 0.1649 + 0.0329 = 3.29
The random number generator seed was not set so in theory you should be be able to reproduce these exact results. Note that the last four results give exactly 3.29, but because of the inexact representation of decimal floating point values, the calculate deviation is not exactly zero. One way around this is to have a very small minimum acceptable deviation. The algorithm is by no means deterministic, because of the random initialisers, and because that is no guarantee that there ever is a solution.
Now I could post the code, but this is not my homework, and so far you have shown little effort. Make a start on this or your own solution and ask for more specific help where necessary.
Clifford
LOL, that's what you do for fun? I'd hate to see what you call "work". :)
It is actually a ton of fun, Math is one of the best ways to exercise your mind. This is a simple polynomial equation.
O_o
^_^
Ha!
Clifford, all your proposed solutions have eleven values.
Anyway, if the values can be negative you'll need to be careful to handle the selection process very carefully--the traditional knapsack approach would fail.
Soma
>> Clifford, all your proposed solutions have eleven values.
Oh yea... so they do!?
Actually that is an issue with the output display rather than the algorithm. The first value is repeated twice. To get the '+''s in the right place I had intended to print the first, then loop printing "+ n". I forgot to modify the loop to start from 1 rather than zero.
"Dumbass-of-the-day" award to me then!
Clifford
^_^
I didn't say there was anything wrong with your algorithm (As I understood it, your proposition is a simplification of one possible implementation of the all-or-nothing algorithm used in the knapsack problem.), but the description of your proposed algorithm could use a little work.
"I forgot to modify the loop to start from 1 rather than zero."
I would have been willing to bet that that was the case.
""Dumbass-of-the-day" award to me then!"
Possibly. With the original preprocessing--no need in starting the algorithm with all that useless data--I envisioned, adding a single negative to the input data would cause all results produced, if any, to be off by (the required number of values)*(the smallest negative number).
Soma
Don't be thinking that my code bares a precise resemblance to the description I gave. The description came off the top of my head as I wrote it. I used it as a starting point and fixed and debugged it as it developed. The OP should perhaps do the same, after all that is a normal part of teh development process.
That said I have not given much thought to how it performs with negative values. I am guessing that the actual implementation works whereas the description does not (not in a position to test it at present).
I am of course reluctant to post the code or elaborate on the algorithm until we see some work from the OP - When do you think his deadline is!?
Clifford
"Don't be thinking [...] development process."
Indeed... which is probably why all the metrics used by management to diagnose a programming project fail to determine anything approaching truth.
"That said I [...] at present)."
I imagine that your implementation, as well as some interpretations of your described algorithm, would work fine for negatives. It all depends on how your 'if' is written. ^_^
It was my, and possibly the OPs assuming he did more than just Google, interpretation of the classic knapsack problem algorithm that has a problem with assuming a positive "weight". (The negative problem inherent in the first draft of my preprocessor is a different issue.)
"I am of course [...] from the OP"
No, you shouldn't do his homework for him (, and neither should anyone else.), but a casual discussion of the merits of our own implementations isn't likely to be detailed enough for the OP to bypass researching an implementation on his own.
"When do you think his deadline is!?"
Knowing the average student... yesterday.
Soma