--- E L I T E ---

Relevant wiki: knapsack problem

This problem is an unbounded knapsack problem. Mathematically formulated we search for numbers $x_i \in \mathbb{N}_0$ , so that $\begin{aligned} \sum_{i = 1}^n v_i \cdot x_i &\stackrel{!}{=} \text{max} \\ \text{while } \sum_{i = 1}^n w_{ji} \cdot x_i &\leq C_j \quad j = 1,\dots,k \end{aligned}$ Here $x_i$ is the quantity of the $i$ -th item. The value $v_i$ corresponds to the profit by the resale of a single item. The weights $w_ {ji}$ correspond respectively to the cost, volume and weight for a single item. The constants $C_j$ are the limits for total cost, total volume, and total weight, that limit the number of items. In our case the values are $\begin{aligned} \left(\begin{array}{c} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \end{array}\right) &= \left(\begin{array}{c} 1 \\ 4 \\ 7 \\ 11 \\ 12 \end{array}\right) \\ \left( \begin{array}{ccccc} w_{11} & w_{12} & w_{13} & w_{14} & w_{15} \\ w_{21} & w_{22} & w_{23} & w_{24} & w_{25} \\ w_{31} & w_{32} & w_{33} & w_{34} & w_{35} \end{array} \right) &= \left( \begin{array}{ccccc} 1 & 3 & 7 & 11 & 13 \\ 13 & 11 & 7 & 3 &1 \\ 7 & 13 & 3 & 7 & 3 \end{array} \right) \\ \left(\begin{array}{c} C_1 \\ C_2 \\ C_3 \end{array}\right) &= \left(\begin{array}{c} 100 \\ 100 \\ 100 \end{array}\right) \end{aligned}$ There are three different solutions for this problem. One of them is the following $\left(\begin{array}{c} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{array}\right) = \left(\begin{array}{c} 1 \\ 3 \\ 5 \\ 5 \\ 0 \end{array}\right)$ so that the total profit results to $\sum_i x_i \cdot v_i = 103$ , while the total weights are $\sum_i w_{ji} \cdot v_i = 100, 96, 96$ .

The solution can be found simply by iterating over all permitted combinations of items. (There is no really efficient algorithm for the knapsack problem, as the problem is NP-complete.) The following program determines the optimal cargo list according to this brute force method:

 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

# DATA INPUT:
items = ["Food", "Alloys", "Computers", "Furs", "Luxuries"] # list of items
weights = [[1,3,7,11,13], [13,11,7,3,1], [7,13,3,7,3]]      # listing of all 'costs' (cost, volume, mass) for each item
limits = [100, 100, 100]                                    # resources (money, tonnage, max. load)
values = [1,4,7,11,12]                                      # profit for each item

# CUSTOM FUNCTIONS:

def dotProduct(x, y):                                       # dot product for two vectors x and y:
    return sum([x[i]*y[i] for i in range(len(y))])          # sum_i x[i]*y[i]

def checkConstraints(c):                                    # Check, if a cargo can be bought and transported
    for i in range(len(weights)):                           # Iterate over all constraints (cost, volume, mass)
        if dotProduct(weights[i], c) > limits[i]:            # Calculate total 'cost' and compare it with resource
            return False                                    # False, if one constraint is not fullfilled
    return True                                             # True, elsewhere

# ALGORITHM (BRUTE FORCE):

cargo, bestCargo = [0] * len(items), [0] * len(items)       # Initialize cargo lists with zeros
maxProfit, index = 0, 0                                     # Initialize target value and item index

while(index < len(items)):                                   # Loop over all possible item combinations (break loop, if index is out of range)
    cargo[index] = cargo[index] + 1                         # Add an extra item to the cargo (of the type items[index])
    if checkConstraints(cargo):                             # Check, if the cargo meets the constraints
        profit = dotProduct(values, cargo)                  # if true, calculate the profit for the cargo and ...
        if profit > maxProfit:                               # ... compare it with the previous maximum
            maxProfit = profit                              # if greater set new maximum and ...
            bestCargo = cargo[:]                            # ... copy cargo list
        index = 0                                           # set index to the first item
    else:                                                   # if the cargo does not meet the constraints...
        cargo[index] = 0                                    # ... remove all elements of the current item and ...
        index = index + 1                                   # ... go the next item

print(dict(zip(items, bestCargo)))
print("Total profit:", maxProfit)

My caveman implementation (yields 103):

Pmax = 0    # max profit seen so far

count = 0   # count millions of loops as a poor man's status bar

for a in range(0,101):          # loop according to upper bounds on each item
    for b in range(0,35):
        for c in range(0,35):
            for d in range(0,35):
                for e in range(0,101):

                    W = 7*a + 13*b + 3*c + 7*d + 3*e    # weight
                    V = 13*a + 11*b + 7*c + 3*d + 1*e   # volume
                    C = 1*a + 3*b + 7*c + 11*d + 13*e   # cost
                    R = 2*a + 7*b + 14*c + 22*d + 25*e  # revenue
                    P = R - C                           # profit

                    if (W <= 100) and (V <= 100) and (C <= 100):  # apply constraints

                        if P > Pmax:                        # update max profit
                            Pmax = P

                    count = count + 1

                    if count % 10**6 == 0:
                        print count / 10**6


print ""
print ""
print Pmax

public class Main {

    public static void main(String[] args){
        System.out.println("The answer is 103.");
    }

}