背包I / O经典问题，以获取价值最低的物品

Question

经典的背包解决了使背包中重量最重的物品能够携带的最有价值的解决方案。

我正在尝试获取价值最低的物品。

以下代码是使用rosetacode http://rosettacode.org/wiki/Knapsack_problem/0-1#Recursive_dynamic_programming_algorithm的递归动态编程的很好的代码>

def total_value(items, max_weight):
    return  sum([x[2] for x in items]) if sum([x[1] for x in items]) <= max_weight else 0

cache = {}
def solve(items, max_weight):
    if not items:
        return ()
    if (items,max_weight) not in cache:
        head = items[0]
        tail = items[1:]
        include = (head,) + solve(tail, max_weight - head[1])
        dont_include = solve(tail, max_weight)
        if total_value(include, max_weight) > total_value(dont_include, max_weight):
            answer = include
        else:
            answer = dont_include
        cache[(items,max_weight)] = answer
    return cache[(items,max_weight)]

items = (
    ("map", 9, 150), ("compass", 13, 35), ("water", 153, 200), ("sandwich", 50, 160),
    ("glucose", 15, 60), ("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40),
    ("cheese", 23, 30), ("beer", 52, 10), ("suntan cream", 11, 70), ("camera", 32, 30),
    ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40),
    ("waterproof trousers", 42, 70), ("waterproof overclothes", 43, 75),
    ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12),
    ("socks", 4, 50), ("book", 30, 10),
    )
max_weight = 400

solution = solve(items, max_weight)
print "items:"
for x in solution:
    print x[0]
print "value:", total_value(solution, max_weight)
print "weight:", sum([x[1] for x in solution])

[我一直试图弄清楚我如何才能在互联网上找到最有价值的物品而没有运气，所以也许有人可以帮助我。

我真的很感谢您的帮助。

经典的背包解决了将最有价值的物品放入背包内的问题，该背包重量有限。我正在尝试获取最有价值的物品。 ...

Answer 1

我将尽最大努力指导您完成该操作。