knapsack-problem.py

#############
# models.py #
#############
from django.db import models


class Goods(models.Model):
    name = models.CharField(max_length=100)    # for example phone, tv etc.
    weight = models.CharField(max_length=100)  # for example 50 kg
    price = models.CharField(max_length=100)   # for example 80 $
    # maybe there can be a piece value too
    # its mean maybe more than one of the same.
    # piece = models.CharField(max_length=100) # for example 2 piece

############
# views.py #
############
from .models import *


# this function finds; which is the most valuable item
def calculate_unit_values(weight, price):
    item_unit_value = int(price) / int(weight)

    return item_unit_value


def solve_knapsack(request):
    # we may also ask to user to enter whatever you want, I will give static value for example 100 kg
    total_weight_capacity = 100

    # first of all we need to find unit values for every item
    items_unit_values = []
    all_objects_list = Goods.objects.all()

    for i in all_objects_list:
        unit_value = calculate_unit_values(i.weight, i.price)
        items_unit_values.append(unit_value)

    # after that finally we know most valuable item
    # and if we want we can sort items_unit_values list
    # Now it is time to fill the bag, starting with the most valuable ones,
    # but not exceed the weight.

    # sorting list descending
    items_unit_values.sort(reverse = True)

    # weight counter for compare total weight
    current_status = 0

    # list of in our knapsack
    in_knapsack = []

    # finding true index value in sorted list
    j = 0

    while current_status <= total_weight_capacity:
        for i in all_objects_list:
            if calculate_unit_values(i.weight, i.price) == items_unit_values[j]:
                current_status += int(i.weight)
                in_knapsack.append(i)
                j += 1

    return in_knapsack