Standard problem of trying to maximize the values of item with a constraint. How many items can you put in a knapsack given the value and the weight of the items.
Uses python3
goal: maximize the value of items selected from the get_optimal_value
while the items selected combined weight is less than the inputted capacity
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import sys from array import array def getIndex(item): return item[0] def getKey(item): return item[1] def get_optimal_value(capacity, weights, values): total_value = 0. values_per_unit = list() # write your code here for counter in range(0, len(weights)): #print(counter, values[counter], weights[counter], values[counter]/weights[counter]) values_per_unit.insert(counter,[counter,values[counter] / weights[counter]]) values_per_unit.sort(key=getKey ,reverse = True) # print(values_per_unit) # grab max of each item until hit capacity for counter in range(0, len(weights)): capacity_to_add = min(capacity, weights[getIndex(values_per_unit[counter])]) #print(capacity, capacity_to_add, values_per_unit[counter]) value_to_add = getKey(values_per_unit[counter]) * capacity_to_add #print("total value: ", total_value, "value to add: ", value_to_add) total_value = total_value + getKey(values_per_unit[counter]) * capacity_to_add capacity = capacity - capacity_to_add if capacity <= 0: return total_value return total_value # user_input_items_n: number of items to choose from # user_input_capacity: total max value of items choosen # item_values: vector, value of item # item_weights: vector, weight of item def user_input(): # get the values from the user data = list(map(int, sys.stdin.read().split())) # split the number of items and weight value user_input_items_n, user_input_capacity = data[0:2] item_values = data[2:(2 * user_input_items_n + 2):2] item_weights = data[3:(2 * user_input_items_n + 2):2] opt_value = get_optimal_value(user_input_capacity, item_weights, item_values) # output the value formatted with 4 decimal points print("{:.4f}".format(opt_value)) # run main program if __name__ == "__main__": user_input() |
Leave a Reply