Question

Hi, I think I need a bit help in ps8.
What is the BruteForce selection method? Basically I know BruteForce is listing all the possible answers, but in this case (the knapsack problem), how do you enumerate all of them when there are like a hundred items...?
And most of all, I don't really understand the algorithm used in problem 3...I ran it but it results in an error (dict doesn't support indexing)
Thanks :)

Answer 1

I've read the brute force method, I can't see what is being indexed, are you using 3.1? have you modified the code, in this assignment brute force adviser should NOT be modified
to answer your question about enumerating the knapsack problems, with a lot of time and computational power.

Answer 2

Here:
else:
s = subject[i]
# Try including subjects[i] in the current working subset.
if subsetWork + s[WORK] <= maxWork:
subset.append(i)
bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue + s[VALUE], subsetWork + s[WORK])
subset.pop()
bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue, subsetWork)
return bestSubset, bestSubsetValue

The part where it says "s = subject[i]" is not working. Apparently the code is trying to assign the first element of the dictionary to s but there is no indexing available in dict = =! Yea I'm using 3.1

Answer 3

http://dpaste.com/557186/
here is how i see it.
The selection is made in lines 19, 26, and 7-13
The first time through (i/index = 0) line 19 is probably executed, it recurses and in that instance of the function line 19 probably gets executed - eventually along that 'recursion path' (i don't know what to call it) the last index is reached- lines 7 thru thirteen are executed and that very last function instance returns something - which allows the next instance up the chain to continue on with the next step (it was essentially 'frozen' till the function it called returned).

notice that line 26 is always executed (not conditional) (except where the index has reached the end). eventually line 26 will be executed by all of the function instances that have been created. this causes a whole new group of function instances (because of the recursion), only this time lines 7-13 have something to compare because bestSubsetValue has a value. also s(WORK) has changed in these new instances so they may not execute line 19 (it is conditional). in any case line 26 is executed by all these new instances but again the circumstances have changed (s(WORK, bestSubsetValue) so this newest new set of function instances will choose different subjects.

repeat the previous paragraph (i was going to say ad infinitum - but hopefully that doesn't happen)

this must go on a lot and it sounds like there will be a lot of duplication of effort. I wonder if there is a way to find out how deep and/or wide the recursions go. Idle has a recursion depth limit of 1000 i think so it must not get that far - each instance dies(?) when it returns

it all sounds very parallel but everything gets processed linearly (i have no idea how parallel processors work) and the function instances get all stacked up and the oldest ones are frozen in time till the newest ones start expiring.

eventually line 30 must get executed by at least the very first function instance (many of the oldest instances must also get to line 30) - supposedly it will be returning a tuple that is optimized for the circumstances that created it

pretty sure i missed something because i can't see yet what exactly that little pop() statement (line 25) accomplishes.

Answer 4

the pop() statement is linked to line 26 always running, notice how it takes best index list and newlist and returns the better, it compares the with_I list to the without_I list. without pop the statements in 26 would be the same as the statement in 19.

OK, i see your problem, the dict.values(), and dict.keys() have changed, no longer created a strait list
http://docs.python.org/release/3.1.3/library/stdtypes.html#dict.values
try replacing the first two lines in the advisor (not the helper) with the ones below
http://dpaste.com/557259/

also looking at the recursion limit of 1000, i'm guessing with the way this code works, you need a list of 1000 (+/-1) to hit that, as it only goes through the entire list once at a time closing each call on a given index before making a new one. the reason something like
def recurse():
recurse()
would hit that limit is that none of the calls are closing.

Answer 5

also sorry poor guy, just wall of text after wall of text

Answer 6

er wow...
I needa take some time to digest all this =D haha

Answer 7

aha.. the pop is in the if clause so that subset is the same in line 26 as line 19- thnx