# Solving the j-th Knapsack Problem using Dynamic Programming

# This is similar to the knapsack problem where we want to fill the container
# with a maximum capacity L_j.

# Instead of maximizing the value, here we want to minimize the preference sum.

import sys

num_customers = 10
preferences_j = []
capacity_l_j = 100
resource_requirement_j = []

# We want to find the assignments X_j.

memory = {}
for i in range(n + 1):
    memory[i] = {}

# We can use the memory dictionary to store the results of the sub-problems
# which we have already solved.

# We can use the DP formula :
# memory[i][j] = For all j: min(memory[i-1][j], memory[i-1][j-r[i]] + preferences[i])

# Initialize the minimum preference sum to the maximum possible amount.
for j in range(capacity_l_j + 1):
    memory[0][j] = sys.maxint

# Iterate through the customer list (1 to n) and possible resource usage sum (0 to capacity)
for i in range(1, num_customers + 1):
    for j in range(0, capacity_l_j):
        if resource_requirement_j[i] <= j:
            memory[i][j] = memory[i - 1][j]
        else:
            memory[i][j] = min(memory[i][j], memory[i-1][j-resource_requirement_j[i] + preferences_j[i])

# The solution of the j-th knapsack problem can be obtained by consdiering all
# the items (n) and the complete capacity of the container (capacity_l_j)

print memory[n][capacity_l_j]