3
\$\begingroup\$

If this question is not a good question for this board, I will remove it. I am looking for ideas on how I could improve the code as I am a beginner trying to learn how to program.

Here I have a program that creates a subproblem for each item that is entered into this function in order to solve a greater problem. I am currently reading a book on algorithms called Grokking Algorithms and he explained this concept and I decided to turn it into code in order to learn.

What the algo does: for each potential item that could go into a bag, it creates an array with the highest value for each amount of pounds the bag can carry. As the algo progresses to the next item, it compares current value of the next item with past maximum values at each pound value to see if it can add to the past maximum value for a given amount of pounds.

I have been programming for less than a year so forgive me if I don't seem to code very well. This is my first dive into dynamic programming.

Anyway, are there any ways that I could have improved the following code to make it more efficient? (Less lines but same type of function)

#This is the code for creating the empty backpack and then filling it with objects

def backpack_creator(size_of_backpacks, amount_of_objects):
    backpack_array = []
    for item in amount_of_objects:
        spaces = []
        for space in range(size_of_backpacks):
            spaces.append(0)
        backpack_array.append(spaces)
    return backpack_array

Backpack = {}
#first value in array is the weight in lbs, second value is actual value
Backpack["water"] = [3, 10]
Backpack["book"] = [1, 3]
Backpack["food"] = [2, 9]
Backpack["jacket"] = [2, 5]
Backpack["camera"] = [1, 6]

empty_backpack = backpack_creator(6,Backpack)
#ending of code to create empty backpack



def backpack_loader(the_items,empty_bag):#this takes the object with the items in it: the_items AND the empty backpack: empty_bag
    bag_to_be_filled = empty_bag
    items_object = the_items
    i = 0
    for item in items_object:
        j = 0
        items_weight = items_object[item][0]
        item_current_value = items_object[item][1]
        for slot in bag_to_be_filled[i]:
            lbs_available_in_slot = j + 1 #because arrays start at 0, a slot cannot be worth 0 pounds so I add one to j
            if i-1 < 0 and lbs_available_in_slot-items_weight >= 0: #if no array can be checked beforehand, take current
                bag_to_be_filled[i][j] = item_current_value
                j += 1
                continue
            elif i-1 < 0 and lbs_available_in_slot-items_weight < 0: #like first if except not enough space for current
                j += 1
                continue
            elif i-1 >= 0 and lbs_available_in_slot-items_weight <= 0: #last array can be checked but not enough space
                old_value = 0
            else:
                #the -1 after items_weight returns lbs_available_in_slot back into array slot value
                #this takes the max value that was found after deducting current weight in the last sub-array
                old_value = bag_to_be_filled[i-1][lbs_available_in_slot-items_weight-1]
            bag_to_be_filled[i][j] = max(bag_to_be_filled[i-1][j], item_current_value + old_value)
            j += 1
        i += 1
    return bag_to_be_filled



loaded_backpack = backpack_loader(Backpack,empty_backpack)
print loaded_backpack
\$\endgroup\$
1

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.