Databases
StackOverflow2013
Postsdbo
POknapsack problem (classic)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POknapsack problem (classic)
    primarykey
    data
    text
    <p>So I have to solve the knapsack problem for class. So far, I've come up with the following. My comparators are functions that determine which of two subjects will be the better option (by looking at the corresponding (value,work) tuples).</p> <p>I decided to iterate over the possible subjects with work less than maxWork, and in order to find which subject is the best option at any given turn, I compared my most recent subject to all the other subjects that we have not used yet.</p> <pre><code>def greedyAdvisor(subjects, maxWork, comparator): """ Returns a dictionary mapping subject name to (value, work) which includes subjects selected by the algorithm, such that the total work of subjects in the dictionary is not greater than maxWork. The subjects are chosen using a greedy algorithm. The subjects dictionary should not be mutated. subjects: dictionary mapping subject name to (value, work) maxWork: int &gt;= 0 comparator: function taking two tuples and returning a bool returns: dictionary mapping subject name to (value, work) """ optimal = {} while maxWork &gt; 0: new_subjects = dict((k,v) for k,v in subjects.items() if v[1] &lt; maxWork) key_list = new_subjects.keys() for name in new_subjects: #create a truncated dictionary new_subjects = dict((name, new_subjects.get(name)) for name in key_list) key_list.remove(name) #compare over the entire dictionary if reduce(comparator,new_subjects.values())==True: #insert this name into the optimal dictionary optimal[name] = new_subjects[name] #update maxWork maxWork = maxWork - subjects[name][1] #and restart the while loop with maxWork updated break return optimal </code></pre> <p>The problem is I don't know why this is wrong. I'm getting errors and I have no idea where my code is wrong (even after throwing in print statements). Help would be much appreciated, thanks!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USGreg Hewgill
    1. USGlassjawed
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POknapsack problem (classic)
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    2. VO
      singulars
      1. POknapsack problem (classic)
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POknapsack problem (classic)
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAre you trying to solve it approximately, or exactly? Because using a simple greedy algorithm will only solve it approximately, and with no guarantees on its quality compared to optimal.
      singulars
      1. POknapsack problem (classic)
      1. USNicholas Mancuso
    2. COHow do you test/run this function? Please add more code.
      singulars
      1. POknapsack problem (classic)
      1. USHamish Grubijan
    3. COI'm only trying to solve it approximately.
      singulars
      1. POknapsack problem (classic)
      1. USGlassjawed
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload