Knapsack

from __future__ import division
from __future__ import print_function

if __name__ == "__main__":
    prices = [70, 85, 145, 260]
    n = int(raw_input("Bitte geben Sie die Gesamtanzahl der Sendungen ein: "))
    e = int(raw_input("Bitte geben Sie den Gesamtbetrag in Cent ein: "))
    print()
    solutions = []

    for w in range(0, n + 1):
        print("Fortschritt: {0:d} %".format(int((w / (n + 1)) * 100)))

        for x in range(0, (n + 1) - w):

            for y in range(0, (n + 1) - (w + x)):
                z = n - (w + x + y)

                if prices[0] * w + prices[1] * x + prices[2] * y + prices[3] * z == e:
                    t = (w, x, y, z)
                    solutions.append(t)

    print()
    print("{:d} Loesungen gefunden.".format(len(solutions)))
    print()

    for solution in solutions:

        for i in range(len(solution)):

            if i > 1:
                print(" + ", end = "")

            print("{:d} * {:d} ct. ".format(solution[i], prices[i]), end = "")

        print()