Q: How can I maximize the value of carried gems with a number and weight restriction? Let's say you have 100 precious gems, each has a weight from 0 to 100, and the value of each could be any positive number. You can only carry 5 of them, and the combined weight can't exceed 30.
How can I pick the gems to carry that will result in the maximum value?
Currently, I have an analogous situation in my project and I'm solving it via brute force. Is there a quicker way?

A: hi this is a very common algorithmic challenge known as the knapsack problem, best solved by dynamic programming:
https://en.wikipedia.org/wiki/Knapsack_problem

A: Refer to 0-1 knapsack problem. Wiki

A: The reason why the naive approach of sorting the gems and choosing the heaviest first won't work is because the heaviest gems may not have the greatest value.  That is why the knapsack algorithm is needed:  it chooses the maximum value that results from either choosing a gem or not choosing a gem.  The next gem or gems may have a greater value than the current gem.  The recursive knapsack solution lools like:
def knapsack(weights, values, capacity, m, count):
    # if no more gems to examine or already chosen 5 gems
    if (m == 0 or count == 5):
        return 0

    # If the gem weight is greater than the capacity
    # try the next gem
    if (weights[m-1] > capacity):  
        return knapsack(weights, values, capacity, m-1, count)  

    # Return the maximum value that results from either choosing the gem
    # or not choosing the gem.
    return max(values[m-1] + knapsack(weights, values, capacity-weights[m-1], m-1, count+1),
               knapsack(weights, values, capacity, m-1, count)


A: You can solve this knapsack problem with either a recursive way or an iterative way, below is a recursive bottom-up method using memoizatoin which I think is the best way to solve this problem.
# w is weights list, v is values list, aw is the total available weight
# i is the number of items (last index of the list)
# m is a dictionary for memoization

def knapsack(w, v, aw, i, m):
    try:
        return m[(i, aw)]
    except KeyError:
        if i == 0:
            if w[i] > aw:
                m[(i, aw)] = 0
                return 0
            else:
                m[(i, aw)] = v[i]
                return v[i]
        without = knapsack(w, v, aw, i-1, m)
        if (w[i] > aw):
            m[(i, aw)] = without 
            return without
        else:
            withi = v[i] + knapsack(w, v, aw-w[i], i-1, m)
            result = withi if withi > without else without
            m[(i, aw)] = result
            return result

