12 KNAPSACK AND GRAPH OPTIMIZATION PROBLEMS

What are the characters of optimization problem?

In general, an optimization problem has two parts:

1. An objective function that is to be maximized or minimized. For example, the airfare¹ between Boston and Istanbul.
2. A set of constraints (possibly empty) that must be honored². For example, an upper bound³ on the travel time.

What’s the main things to take away from this chapter?

• Many problems of real importance can be formulated in a simple way that leads naturally to a computational solution.
• Reducing a seemingly new problem to an instance of a well-known problem allows one to use preexisting solutions.
• Knapsack problems and graph problems are classes of problems to which other problems can often be reduced.
• Exhaustive enumeration algorithms provide a simple, but often computationally intractable, way to search for optimal solutions.
• A greedy algorithm is often a practical approach to finding a pretty good, but not always optimal, solution to an optimization problem.

12.1 Knapsack⁴ Problems

Why it is not easy being a burglar?

In addition to the obvious problems (making sure that a home is empty, picking locks, circumventing alarms, dealing with ethical quandaries, etc.), a burglar has to decide what to steal. The problem is that most homes contain more things of value than the average burglar can carry away. What’s a poor burglar to do? He needs to find the set of things that provides the most value without exceeding his carrying capacity. Suppose for example, a burglar who has a knapsack that can hold at most 20 pounds of loot⁵ breaks into a house and finds the items in Figure 12.1. Clearly, he will not be able to fit it all in his knapsack, so he needs to decide what to take and what to leave behind.

	Value	Weight	Value/Weight
Clock	175	10	17.5
Painting	90	9	10
Radio	20	4	5
Vase	50	2	25
Book	10	1	10
Computer	200	20	10

Figure 12.1 Table of items

What is the basic concept behind greedy algorithm?

The thief would choose the best item first, then the next best, and continue until he reached his limit. Of course, before doing this, the thief would have to decide what “best” should mean. Is the best item the most valuable, the least heavy, or maybe the item with the highest value-to-weight ratio?

Don’t under look a greedy algorithm. It is an algorithm:

• It sets the ruler to compare: the best.
• It shows the order of actions: one by one.
• It puts clear boundary: carry weight.

What is the implementation of three “best” greedy algorithm?

class Item (object):
    """
    Class of loot item, including three attributes: <name, value, and weight>.
    """

    def __init__(self, n, v, w):
        """
        Init a instance of Item with name, value and weight.
        :param n: string, name of item
        :param v: float, value of item
        :param w: float, value of item
        """
        self.name = n
        self.value = v
        self.weight = w

    def getName (self):
        return self.name

    def getValue (self):
        return self.value

    def getWeight (self):
        return self.weight

    def __str__(self):
        result = '<' + self.name + ', ' + str (self.value)\
                 + ', ' + str (self.weight) + '>'
        return result


def value (item):
    """
    Map "item" into its value.
    :param item: an Item type item
    :return: this item's value
    """
    return item.getValue ()


def weightInverse (item):
    """
    Map "item" into its weight's inverse value.
    :param item: an Item type item
    :return: this item's 1/weight
    """
    return 1.0/item.getWeight ()


def density (item):
    """
    Map "item" into its density(value/weight).
    :param item: an Item type item
    :return: this item's value/weight
    """
    return item.getValue ()/item.getWeight ()


def greedy (items, maxWeight, keyFunction):
    """
    Greedy is the core process of greedy algorithm. According to the keyFunction,
    it puts the best items into knapsack until it is full.
    :param items: list, of instances of Item.
    :param maxWeight: float >= 0, the maximum weight a knapsack can contain.
    :param keyFunction: function,
    maps an item in a list to an comparable value accordingly,
    as the second parameter of the `sorted` function
    :return: a list of taken items, and a float of their total value
    """
    # Use "what is my best" as the key function to sort a copied list of the items.
    # Note the `sorted`'s algorithm efficiency is in O(n * log(n)).
    itemsCopy = sorted (items, key = keyFunction, reverse = True)
    result = []
    totalValue, totalWeight = 0.0, 0.0
    # Try each item in the sorted items list descendingly.
    for i in range (len (itemsCopy)):
        # Check whether the next biggest one could be taken into knapsack.
        if (totalWeight + itemsCopy[i].getWeight ()) <= maxWeight:
            result.append (itemsCopy[i])
            # If new item is taken, update the total weight and value of result
            totalWeight += itemsCopy[i].getWeight ()
            totalValue += itemsCopy[i].getValue ()
    return result, totalValue


def build_items ():
    """
    Build a list of Items instances.
    :return: a list of Items instances.
    """
    names = ['clock','painting','radio','vase','book','computer']
    values = [175,90,20,50,10,200]
    weights = [10,9,4,2,1,20]
    items = []
    for i in range (len(values)):
        items.append (Item(names[i], values[i], weights[i]))
    return items


def test_greedy (items, maxWeight, keyFunction):
    """
    Calculate for one sort of greedy strategy, and print its result.
    :param items: a list of Items instances.
    :param maxWeight: float, as the maximum weight a knapsack can hold.
    :param keyFunction: function,
    maps an item in a list to an comparable value accordingly,
    as the second parameter of the `sorted` function
    :return: None. Print out total value and items in taken loot.
    """
    taken, val = greedy (items, maxWeight, keyFunction)
    print ('Total value of items taken is', val)
    for item in taken:
        print (' ', item)


def test_diff_greedys (maxWeight = 20):
    """
    Print out the results of different sorts of greedy strategy.
    :param maxWeight: float, as the maximum weight a knapsack can hold,
    with default value 20.0.
    :return: None. Print out total value and items in taken loot of three sorts of strategy.
    """
    items = build_items ()
    # Greedy by value.
    print ('Use greedy by value to fill knapsack of size', maxWeight)
    test_greedy (items, maxWeight, value)
    # Greedy by weight.
    print ('\nUse greedy by weight to fill knapsack of size',
          maxWeight)
    test_greedy (items, maxWeight, weightInverse)
    # Greedy by density.
    print ('\nUse greedy by density to fill knapsack of size',
          maxWeight)
    test_greedy (items, maxWeight, density)

Here we run it.

test_diff_greedys(maxWeight=20.0)

How to formalize the 0/1 knapsack problem as an instance of a classic optimization problem?

The 0/1 knapsack problem can be formalized as follows:

1. Each item is represented by a pair, <value, weight>.
2. The knapsack can accommodate items with a total weight of no more than w.
3. A vector, I, of length n, represents the set of available items. Each element of the vector is an item.
4. A vector, V, of length n, is used to indicate whether or not each item is taken by the burglar. If V[i] = 1, item I[i] is taken. If V[i] = 0, item I[i] is not taken.
5. Find a V that maximizes

\[ \sum_{i=0}^{n-1} V[i]^{*} I[i] . \text { value } \]

​ subject to the constraint that \[ \sum_{i=0}^{n-1} V[i] * I[i] . \text {weight} \leq w \]

How to implement the 0/1 knapsack problem’s formalization which is inherently exponential in the number of items in a straightforward way?

def get_binary_rep(positive_integer: int, num_bi_digits: int):
    """
    Get int n's binary representation in a fix binary digits with leading zeros.
    :param positive_integer: int, a non-negative decimal integer to be turned into binary number.
    :param num_bi_digits: int, a non-negative decimal integer to set a fixed length of the
    resulting binary number digits. It should be big enough.
    :return: a string of '0's and '1's of length numDigits that is a binary representation
    of n.
    """
    binary_str = ''
    while positive_integer > 0:
        binary_str = str(positive_integer % 2) + binary_str
        positive_integer = positive_integer // 2
    if len(binary_str) > num_bi_digits:
        raise ValueError('not enough digits')
    for i in range(num_bi_digits- len(binary_str)):
        binary_str = '0' + binary_str
    return binary_str

def gen_power_set (ori_list): # O(2**len(ori_list)) * O(len (ori_list))
    """
    Generate the power set of ori_list, including all subsets of the set of
     ori_list's items.
    E.g., if ori_list is [1, 2] it will return a list with elements
    [], [1], [2], and [1,2].
    Recall that every set is a subset of itself and the empty set is a subset of every set.
    So the length of the power set is 2**len(ori_list).
    :param ori_list: list
    :return: a list of lists that contains all possible combinations of
    the elements of ori_list.
    """
    power_set = []
    for i in range (0, 2**len(ori_list)): # O(2**len(ori_list))
        bin_str = get_binary_rep(i, len(ori_list))
        subset = []
        for j in range(len(ori_list)): # O(len(ori_list))
           if bin_str[j] == '1':
              subset.append(ori_list[j])
        power_set.append(subset)
    return power_set

def choose_best(pset, max_weight, get_val, get_weight):
    """
    Choose the best set of items from the power set of original list,
    within the maximum weight budget of knapsack.
    :param pset: list of lists, that contains all possible combinations of
    the elements of ori_list.
    :param max_weight: float or int, maximum weight budget of knapsack.
    :param get_val: function or method, map an item in pset's list into its
    comparable value
    :param get_weight: function or method, map an item in pset's list into its
    comparable weight
    :return: a best set of items, and this best set's total value
    """
    best_val = 0.0
    best_set = None
    for items in pset:
        items_val = 0.0
        items_weight = 0.0
        for item in items:
            items_val += get_val(item)
            items_weight += get_weight(item)
        if items_weight <= max_weight and items_val > best_val:
            best_val = items_val
            best_set = items
    return best_set, best_val

def test_best(max_weight = 20):
    """
    Run the choose_best function, and print its result in proper format.
    :param max_weight: float or int, maximum weight budget of knapsack, default 20.
    :return: None, print out the items taken and their total value.
    """
    items = build_items()
    pset = gen_power_set(items)
    taken, val = choose_best(pset, max_weight, Item.getValue, Item.getWeight)
    print('Total value of items taken is', val)
    for item in taken:
        print(item)

Run test_best script.

test_best(max_weight=20)

This result is different from the result of density.

Could this straightforward way be speeded up?

01.The gen_power_set could have had the header

def genPowerset(items, constraint, getVal, getWeight)

and returned only those combinations that meet the weight constraint.

Or

02.The choose_best could exit the inner loop as soon as the weight constraint is exceeded.

# def gen_power_set (ori_list): # O(2**len(ori_list)) * O(len (ori_list))
def gen_power_set_within_constraint(items, constraint, getWeight):
    """
    Generate the power set of items which meet the weight constraint.
    :param items: list, instances of Items.
    :param constraint: float, maximum weight of knapsack.
    :param getWeight: method, get weight of an Item.
    :return: a list of lists that contains all possible combinations of
    the elements that meet the weight constraint.
    """
    power_set_within_constraint = []
    for i in range (0, 2**len(items)): # O(2**len(ori_list))
        bin_str = get_binary_rep(i, len(items))
        subset = []
        subset_total_weight = 0
        for j in range(len(items)): # O(len(ori_list))
            if bin_str[j] == '1':
                subset.append(items[j])
                subset_total_weight += items[j].getWeight()
        if subset_total_weight <= constraint:
            power_set_within_constraint.append(subset)
    return power_set_within_constraint

# def choose_best(pset, max_weight, get_val, get_weight):
def choose_best_efficiently(pset, max_weight, get_val, get_weight):
    """
    Choose the best set of items from the power set of original list,
    within the maximum weight budget of knapsack.
    :param pset: list of lists, that contains all possible combinations of
    the elements of ori_list.
    :param max_weight: float or int, maximum weight budget of knapsack.
    :param get_val: function or method, map an item in pset's list into its
    comparable value
    :param get_weight: function or method, map an item in pset's list into its
    comparable weight
    :return: a best set of items, and this best set's total value
    """
    best_val = 0.0
    best_set = None
    for items in pset:
        items_val = 0.0
        items_weight = 0.0
        for item in items:
            items_val += get_val(item)
            items_weight += get_weight(item)
            if items_weight > max_weight:
                break
        if items_weight <= max_weight and items_val > best_val:
            best_val = items_val
            best_set = items
    return best_set, best_val

# def test_best(max_weight = 20):
def test_best_opt_01(max_weight = 20):
    """
    Run the choose_best function, and print its result in proper format.
    :param max_weight: float or int, maximum weight budget of knapsack, default 20.
    :return: None, print out the items taken and their total value.
    """
    items = build_items()
    pset_within_constraint = gen_power_set_within_constraint(items, constraint=max_weight, getWeight=Item.getWeight)
    taken, val = choose_best(pset_within_constraint, max_weight, Item.getValue, Item.getWeight)
    print('Total value of items taken is', val)
    for item in taken:
        print(item)

# def test_best(max_weight = 20):
def test_best_opt_02(max_weight = 20):
    """
    Run the choose_best function, and print its result in proper format.
    :param max_weight: float or int, maximum weight budget of knapsack, default 20.
    :return: None, print out the items taken and their total value.
    """
    items = build_items()
    pset = gen_power_set(items)
    taken, val = choose_best_efficiently(pset, max_weight, Item.getValue, Item.getWeight)
    print('Total value of items taken is', val)
    for item in taken:
        print(item)

test_best_opt_01(max_weight=20)

test_best_opt_02(max_weight=20)

While these kinds of optimizations are often worth doing, they don’t address the fundamental issue. 【吴军老师写好算法后，工程主管要他做优化，省机器就是算钱。】

```

---

1. airfare: the price to be paid by an aircraft passenger for a particular journey: save a bundle in airfare by flying standby.↩

2. honor_v.t.: make sure the franchisees honour the terms of the contract: fulfil, observe, keep, discharge, implement, perform, execute, effect, obey, heed, follow, carry out, carry through, keep to, abide by, adhere to, comply with, conform to, act in accordance with, be true to, be faithful to, live up to; rare effectuate. ANTONYMS disobey.↩

3. Syn. – Limit; bound; border; term; termination; barrier; verge; confines; precinct. Bound, Boundary. Boundary, in its original and strictest sense, is a visible object or mark indicating a limit. Bound is the limit itself. But in ordinary usage the two words are made interchangeable.↩

4. knapsack: noun RUCKSACK, BACKPACK, haversack, pack, kitbag, duffel bag, satchel, shoulder bag; British holdall.↩

5. loot: Plunder; booty; especially, the booty taken in a conquered or sacked city.↩