Computer Science Canada Dynamic Programming Problem |

Author: | saltpro15 [ Wed Sep 30, 2009 3:29 pm ] |

Post subject: | Dynamic Programming Problem |

Hey all, So my CS teacher gave me an idea for a knapsack DP problem, and I put a bit of a twist on it (Can't make things too easy now!). Here it is in .odt and .pdf form. Please don't post solutions here, as it rather ruins it for other people, but you are welcome to discuss it p.s. Sorry if this is in the wrong forum... general programming wouldn't let me add an attachment >.< |

Author: | A.J [ Wed Sep 30, 2009 9:20 pm ] |

Post subject: | RE:Dynamic Programming Problem |

Mr. Hughes has posed this problem to me about a year ago actually. A pretty straightforward problem. |

Author: | Cyril [ Wed Sep 30, 2009 10:36 pm ] |

Post subject: | RE:Dynamic Programming Problem |

Since there are only 19 different ages, take the top 4 of each age, and use brute force. 76 choose 4 is very small. You should probably change some bounds... |

Author: | A.J [ Thu Oct 01, 2009 8:50 am ] |

Post subject: | RE:Dynamic Programming Problem |

@Cyril- I thought he said that he didn't want us to post solutions here... |

Author: | saltpro15 [ Thu Oct 01, 2009 12:15 pm ] |

Post subject: | RE:Dynamic Programming Problem |

Brute forcing would be O(N^2) complexity right? With N = 5000, that probably won't run in a second. An O(N*M) DP algorithm is still needed. I'll make a giant test case though to make sure the brute forcing solutions will fail |

Author: | bbi5291 [ Thu Oct 01, 2009 3:34 pm ] |

Post subject: | Re: RE:Dynamic Programming Problem |

saltpro15 @ Thu Oct 01, 2009 12:15 pm wrote:Brute forcing would be O(N^2) complexity right? With N = 5000, that probably won't run in a second.
No, I think 25 million operations in a second is reasonable on a fast computer. Depends on what they are, of course. |

Author: | A.J [ Thu Oct 01, 2009 7:02 pm ] |

Post subject: | RE:Dynamic Programming Problem |

Once again guys, isn't it against 'protocol' ( had to use that word) to post possible solutions here? And Drew, the DP solution isn't all that bad. And, once again, ask Mr.Hughes if it is possible for you guys to make a trip here (as we can't make it there due to lack of a CS teacher at our school, and lack of funding). |

Author: | saltpro15 [ Thu Oct 01, 2009 7:03 pm ] |

Post subject: | RE:Dynamic Programming Problem |

AJ, I'll PM you what I've done so far tomorrow, as the code is saved on my school account. I have this basically done |

Author: | md [ Thu Oct 01, 2009 10:02 pm ] |

Post subject: | RE:Dynamic Programming Problem |

Moved to a more appropriate forum. I don't think discussing posibilities or directions at a solution is the same as posting an actual solution. Though 25 million posibilities is quite a bit - brute force might work but definitely not the way to go. |

Author: | bbi5291 [ Thu Oct 01, 2009 10:31 pm ] |

Post subject: | Re: Dynamic Programming Problem |

md wrote:Moved to a more appropriate forum. I think this thread should go in General Programming. It really doesn't have anything to do with C++ in particular. |

Author: | Cyril [ Sat Oct 03, 2009 12:16 am ] |

Post subject: | RE:Dynamic Programming Problem |

Well, I don't think it's inappropriate to post solutions that have nothing to do with the title of the thread. Since we're not posting the intended algorithms, I think it counts as discussion, rather than giving away the DP solution. |

: |

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.