cake: knapsack

[nmusgrave]

# cake tuples: (weight, value)
def max_duffel_bag_value(cakes, weight_capacity):
    # greatest value possible for some weight i
    opt = []
    opt.append(0)
    for i in range(1, weight_capacity + 1):
        value = opt[i - 1]
        for cake in cakes:
            if cake[0] <= i:
                value = max(value, opt[i - cake[0]] + cake[1])
        opt.append(value)
    return opt[weight_capacity]

cake_tuples = [(7, 160), (3, 90), (2, 15)]
capacity    = 20

print(max_duffel_bag_value(cake_tuples, capacity))
# returns 555 (6 of the middle type of cake and 1 of the last type of cake)

[nmusgrave]

cake: stack using 2 queues import queue ''' Implement stack using 2 queues assume queue gives O(1) push and pop ''' class Stack: def init(self): self.q1 = queue.Queue() self.q2 = queue.Queue() self.size = 0

    # insert at top of stack
    def push(self, value):
        self.q1.put(value)
        self.size += 1

    # remove from top of stack
    def pop(self):
        self.q2.empty()
        for i in range(self.size - 1):
            self.q2.put(self.q1.get())
        result = self.q1.get()
        assert(self.q1.empty())
        self.size = self.size - 1
        for i in range(self.size):
            self.q1.put(self.q2.get())
        assert(self.q2.empty())
        return result

s = Stack()
s.push(4)
s.push(5)
print(s.pop(), ' == 5?')
print(s.pop(), ' == 4?')