table.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import print_function
from collections import deque
from collections import namedtuple
from pprint import pprint


Item = namedtuple('Item', 'value weight')
Item.__repr__ = lambda self: '({}v, {}w)'.format(self.value, self.weight)


def col(item, K, prev):
    '''
    Compute a column for `item`.  In our table each column represents
    an item and each row -- a capacity.  Each cell of the column says
    what's the greatest achievable value for respective capacity with
    or without the inclusion of `item`.

    Args:
      - item:
      - K: Max capacity
      - prev: Column for previous item (if that's the first item, this
              should be all zeros).
    '''
    for cap in range(K):
        # Case 1: weight is less than current capacity, so keep
        # previous.
        if cap < item.weight:
            yield prev[cap]
        else:
            #
            # Case 2: Adding this item gives better value.
            val = prev[cap - item.weight] + item.value
            if val > prev[cap]:
                yield val
            #
            # Case 3: Adding this item doesn't give better value, so
            # we keep what we currently have.
            else:
                yield prev[cap]


def compute_table(items, K):
    # First column of M is all zeros.
    c = [0] * K
    M = [c]

    # For each item, create a table column and add it to M.
    for index, _ in enumerate(items):
        c = list(col(items[index], K, c))
        M.append(c)

    return M


def traceback(M, items, K):
    ans = deque()
    cap = K - 1

    # Each column in M represents an item.  Each row represents
    # capacity.  Loop from last column to first and track which items
    # got added.
    for current in range(len(M)-1, 0, -1):
        i = current - 1     # Item index
        prev = current - 1  # Previous column

        if M[prev][cap] == M[current][cap]:
            ans.appendleft(0)
        else:
            cap -= items[i].weight
            ans.appendleft(1)

    return ans


def getinput(case=0):
    # value, weight
    if case == 0:
        items = [
            Item(5, 4),
            Item(6, 5),
            Item(3, 2)
        ]
        K = 9
    elif case == 1:
        items = [
            Item(16, 2),
            Item(19, 3),
            Item(23, 4),
            Item(28, 5)
        ]
        K = 7
    elif case == 2:
        items = [
            Item(45, 5),
            Item(48, 8),
            Item(35, 3)
        ]
        K = 10
    else:
        raise ValueError
    return (items, K + 1)


def main():
    items, K = getinput(2)
    M = compute_table(items, K)

    print('Items:')
    pprint(items)
    print()

    print('Tables:')
    # zip() is used to transpose the matrix
    T = zip(*M)
    pprint(list(T))
    print()

    print('Traceback:')
    pprint(traceback(M, items, K))
    # pprint(traceback2(M, items, K))


if __name__ == '__main__':
    main()