[racshot65]

Hi,

I'm currently going through MIT's open courseware course on programming and I'm stuck on this assignment:

http://ocw.mit.edu/N...DBE/0/pset6.pdf

(Problem 3)

Basically you have a hand of letters and need to get the computer to make a word from those letters that scores the most points


I have the dictionary mapping the words to their point value but I don't know how I can make the computer pick the best word from my hand ?


Any Ideas ?

Thanks

[Martyr2]

Its the knapsack problem in disguise (the 0:1 variation sounds right). The knapsack size is the number of letters you have total. How many letters can you fit in it that also form a word to maximize their value. The idea is that you are going to run across all the combination of the letters possible, determining if it is a word, and if so also add up its value. A greedy algorithm would say grab as many letters and take the longest word, but that isn't necessarily going to be the most valuable. A shorter word may use more exotic letters and increase its value.

So look at the solution for the knapsack problem and you will see your solution to this data set.

[racshot65]

Hi,

Thanks for your reply.

Is a different but maybe less efficient way ?

The reason I say this is that based on the course calendar they don't teach the knapsack problem for another two lectures and this should be done before the next one

[FXRev]

Isn't the Knapsack problem a NP-Complete?

[KYA]

If you try to solve it "exactly". 0-1 or close enough can be done in polynomial time.