Too techie.. is there an easier method?
Moderators: Section Moderators, Forum Moderators
Too techie.. is there an easier method?
Can someone tell me how to explain my DD questions like this?
All bridges must have 2 section A's (in the start and end) and nowhere else. Length of individual sections is as follows:
Section A - 8.19m, B - 5.21m, C=2.91m, D=3.64m, E=7.52m, F=2.40m
Find the best combination of sections that will make the following bridges.
a) 44.18m
b) 65m
c) 94m
I know the following:
1) 2 section A's = 8.19 + 8.19 = 16.38
2) For (a) then the length required becomes 44.18 - 16.38 = 27.80
Now how to get the other sections add upto 27.8?
All bridges must have 2 section A's (in the start and end) and nowhere else. Length of individual sections is as follows:
Section A - 8.19m, B - 5.21m, C=2.91m, D=3.64m, E=7.52m, F=2.40m
Find the best combination of sections that will make the following bridges.
a) 44.18m
b) 65m
c) 94m
I know the following:
1) 2 section A's = 8.19 + 8.19 = 16.38
2) For (a) then the length required becomes 44.18 - 16.38 = 27.80
Now how to get the other sections add upto 27.8?
This is an example of what's known in the computing literature as a Knapsack Problem. It's one of a large class of problems (the NP-complete problems, also including the Travelling Salesman Problem) that are known to be equally hard, but no-one knows whether there is an efficient way to solve them. That question is one of the Millenium Prize Problems. Most people think the answer is no, but no-one has proved it.
In short, I think BarnetDad's advice is sound.
But then the one thing I can't resist is temptation, so, getting a computer to try all the possibilities:
a) 5D + 4F (unique solution)
b) 3B + C + 4E (shortest solution)
c) 2B + 4D + 7E or 6C + 8E (shortest solutions)
(It's typical of NP-complete problems that it's easy to check solutions, but the number of potential solutions to check is very large.)
In short, I think BarnetDad's advice is sound.
But then the one thing I can't resist is temptation, so, getting a computer to try all the possibilities:
a) 5D + 4F (unique solution)
b) 3B + C + 4E (shortest solution)
c) 2B + 4D + 7E or 6C + 8E (shortest solutions)
(It's typical of NP-complete problems that it's easy to check solutions, but the number of potential solutions to check is very large.)
This kind of question should be kept until your DD finishes all others. Here is what I think from what you have done for a)
If you take a look at 27.80 m, you will see that you require the last digit as 0.
Now look at each section
B = 5.21m - you need 10B to make the last digit = 0 ... No (52.10m)
C = 2.91m - you need 10C to make the last digit = 0 ... No (29.10m)
D = 3.64m - you need 5D to make the last digit = 0 ... Yes - 3.64x5 = 18.20m
E = 7.52m - you need 5E to make the last digit = 0 ... No (37.6m)
F = 2.40m - you always have the last digit = 0 ... Yes
So 27.80 - 18.20 = 9.60m
Then 2.40m x 4 = 9.60m
Answer 5D + 4F
For b) and c) you have to start from the biggest section, E.
If you take a look at 27.80 m, you will see that you require the last digit as 0.
Now look at each section
B = 5.21m - you need 10B to make the last digit = 0 ... No (52.10m)
C = 2.91m - you need 10C to make the last digit = 0 ... No (29.10m)
D = 3.64m - you need 5D to make the last digit = 0 ... Yes - 3.64x5 = 18.20m
E = 7.52m - you need 5E to make the last digit = 0 ... No (37.6m)
F = 2.40m - you always have the last digit = 0 ... Yes
So 27.80 - 18.20 = 9.60m
Then 2.40m x 4 = 9.60m
Answer 5D + 4F
For b) and c) you have to start from the biggest section, E.
It's a lot harder than that. You've assumed that two numbers ending in 0 were added to get the final 0, but it could have been one ending in 6 and another ending in 4, etc. And it could have been adding three, four or five numbers.Crazydad wrote:If you take a look at 27.80 m, you will see that you require the last digit as 0.
-
- Posts: 1245
- Joined: Fri Jul 06, 2007 9:31 pm
I have a heuristic method that meant I got at least some of the answers without trying all possibilities...
Here's how it works.. Assume 2A
Take all the other lengths and sort in descending length... giving order.. 7.52, 5.21, 3.64, 2.91, 2.4
Now choose the most of the biggest length that fits the remaining gap and then successively allocate the remainder using the next size down, when there is a remainder reduce the larger size and use a multiple of a smaller size...
I'm not sure such an approach works but I have just deduced that
44.18 is 2x8.19 + 5x3.64 and 4x2.4 without enumerating all the possibilities....
Here's how it works.. Assume 2A
Take all the other lengths and sort in descending length... giving order.. 7.52, 5.21, 3.64, 2.91, 2.4
Now choose the most of the biggest length that fits the remaining gap and then successively allocate the remainder using the next size down, when there is a remainder reduce the larger size and use a multiple of a smaller size...
I'm not sure such an approach works but I have just deduced that
44.18 is 2x8.19 + 5x3.64 and 4x2.4 without enumerating all the possibilities....
Animis opibusque parati
-
- Posts: 1245
- Joined: Fri Jul 06, 2007 9:31 pm
-
- Posts: 1245
- Joined: Fri Jul 06, 2007 9:31 pm
-
- Posts: 1245
- Joined: Fri Jul 06, 2007 9:31 pm