如何用两个参数计算最大背包解

2024-03-28 22:45:48 发布

您现在位置:Python中文网/ 问答频道 /正文

我之前提出的问题,花了我一段时间用两个参数来解决,但最终得到了它。在这里为可能需要它的任何其他人发布

“你有一个能装W总重量的袋子,在你面前放着一系列你想放进袋子里的东西。每件物品都有一个重量和一个与之相关的值,您希望在袋子中放入尽可能多的总价值,而总重量不超过袋子所能容纳的容量W

在名为code.py的文件中编写一个Python程序来完成此任务。您应该编写一个函数fill_sack(W,items),该函数以sack容量W和(weight,value)对列表作为输入,并返回可以放入袋子中的最大值。提供了几个测试用例。”

def fill_sack(W, items):
    weight, value = map(list, zip(*items))
    n = len(value)
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(n + 1): 
        for w in range(W + 1): 
            if i == 0 or w == 0: 
                K[i][w] = 0
            elif weight[i-1] <= w: 
                K[i][w] = max(value[i-1] + K[i-1][w-weight[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
    return K[n][W] 

Tags: 函数infor参数valueitemsrangefill