enter code here我有这样一个df:
Project position emp hrs
0 A Burger flipper John 1.25
1 B cashier steve 2.25
2 C cleaner Karen 0.25
3 A shift manager sally 0.25
4 C supervisor julie 1.25
5 A cleaner Karen
我最近的实验任务让我尝试实现0/1背包问题的贪婪算法,并打印出背包的内容以及背包的总价值。到目前为止,我可以让它输出背包的总价值,但我在输出背包中的物品时遇到了问题。 #class definitions for the greedy approach
class Item:
def __init__(self,weight,value):
self.weight = weight
self.value = value
self.price_kg = value / weight
def __repr__(self):
我很好奇是否可以修改(或使用)无界背包问题的DP算法,以使背包中项目的总价值最小化,同时使总重量至少为最小约束C。
UKP最大化版本的自下而上DP算法:
let w = set of weights (0-indexed)
and v = set of values (0-indexed)
DP[i][j] = max{ DP[i-1][j], DP[i][j - w[i-1]] + v[i-1] }
for i = 0,...,N and j = 0,...,C
given DP[0][j] = 0 and DP[i][0] = 0
where N = amount of
这是一个古老而著名的背包问题:
这里我有一个约束的背包问题。
我有大小为W = 100000000和N = 100的背包,我为其编写了动态解决方案,我的算法的复杂性是O(100000000*100),这在时间和空间上都太大了,但是这里有一个条件,即无论是W ≤ 50000 or max 1≤ i ≤ n Vi ≤ 500.还是W ≤ 50000 or max 1≤ i ≤ n Vi ≤ 500.,所以如果背包大小超过50000,则项目的最大值是有限的。
所以,现在我想知道,在这种情况下,如何降低算法的时间复杂度?我认为背包问题取决于背包的大小和项目的数量,那么项的值如何改变我的算法?