[已解决]Python：每日一题 329

zltzlt

776667 发表于 2020-2-11 21:16

超时

zltzlt

546623863 发表于 2020-2-11 21:40
动态规划吧

输入大数据超出内存限制

zltzlt

坑得飞起 发表于 2020-2-11 22:01
def func(s,v,c):
    danjia, ans =[], 0
    for i in range(len(c)):

解答错误

输入：

s = 195387950,
v = [277996895,67034365,215265173,17927245,196665561,122553408,229181848,37953684,130611629,18096518,221937650,16569090,215131206,246680015,75894559,177999561,249070738,321264238,110845985,176753214],
s = [228482420,301972492,81534843,235620330,102486915,234004708,18881095,194477148,60832041,118314582,292428017,74861428,43938149,86992501,239732394,193891049,112838218,127944264,276821750,172241156]

输出：690993069
预期结果：765577292

zltzlt

William4869 发表于 2020-2-11 22:10
无脑深搜遍历玩法，感觉会超时，，回头我去看看动态规划是个什么东西

超时

zltzlt

fan1993423 发表于 2020-2-11 23:26
我不知道要不要考虑背包装不下任何东西的情况，为了保守起见，还是多加个判别式

60 ms

zltzlt

kinkon 发表于 2020-2-11 23:59

会超时

zltzlt

ouyunfu 发表于 2020-2-12 01:07
s = 10
v = [1,2,3,4]
c = [3,5,7,3]

https://fishc.com.cn/forum.php?m ... peid%26typeid%3D441

zltzlt

ouyunfu 发表于 2020-2-12 01:07
s = 10
v = [1,2,3,4]
c = [3,5,7,3]

会超时

zltzlt

TJBEST 发表于 2020-2-12 11:57
第二个版本，背包求解，没用递归，挺快的

超出内存限制

zltzlt

TJBEST 发表于 2020-2-11 23:31
先来个简单的 背包问题的分治算法 我忘了 先用这个试试 分治算法我再看看
#给出一个非负整数 s  ...

超时

坑得飞起

坑得飞起 发表于 2020-2-11 22:01
def func(s,v,c):
    danjia, ans =[], 0
    for i in range(len(c)):

按照单价（v/c）从大到小排序后用贪心算法不香吗，代码比穷举或动归的好写多了

fan1993423

zltzlt 发表于 2020-2-12 14:27
60 ms

是不是只有我一个没有超时啊

zltzlt

fan1993423 发表于 2020-2-12 15:07
是不是只有我一个没有超时啊

是

TJBEST

zltzlt 发表于 2020-2-12 14:31
超出内存限制

超出内存？我的空间 是o(n)的 n是个数 不应该吧

坑得飞起

fan1993423 发表于 2020-2-12 15:07
是不是只有我一个没有超时啊

你的算法是什么？

zltzlt

TJBEST 发表于 2020-2-12 15:27
超出内存？我的空间 是o(n)的 n是个数 不应该吧

因为 n 很大

fan1993423

坑得飞起 发表于 2020-2-12 16:04
你的算法是什么？

这道题是想求最大价值物品，所以我们要尽可能要价值最大的物品排在前面，然后V和C是有对应关系的，本来应该是建立V和C的字典关系，但是后来考虑下没必要。S是我们背包放的总重量，也就是最大累计放的C，count用来计数，for i循环是为了指出起点位置，for j循环是在起始点位置情况下，慢慢移动终点位置，只要这个s还大于0，即还可以装东西，我们就让他贪婪的装，count就加上这个数V,如果装的那个东西太大，那么我们就让他取出来，也就是这个s要把刚才减掉的数加回来。result是每次和count比较，取最大值，它是所有的结果的最大值，只是每次循环要让count清零，让s重新回到初始值。

TJBEST

zltzlt 发表于 2020-2-12 16:15
因为 n 很大

您在试试这个，我尝试缩小了点空间

def fun329(s,v,c):
    #0/1背包问题 由于 给的条件没有说 每个同体积同价值的个数（或无限） 只能按照0/1背包去算
    #采用循环遍历 
    #s是容量 v是价值 c是体积
    M = len(v)
    f = {}
    
    for i in range(0,M):
        AList = list(f.keys())
        BList = list(map(lambda x:c[i] + x,AList))
        BList.append(c[i])
        keyList = sorted(set(AList + BList))
        keyList.reverse()
        for each in keyList:
            if each > s:
                pass
            else:
                if (each in AList) and (each in BList):
                    try:
                        f[each] = max([f[each],f[each - c[i]] + v[i]])
                    except Exception:
                        f[each] = max([f[each],v[i]])
                elif (each in BList):
                    try:
                        f[each] = f[each - c[i]] + v[i]
                    except Exception:
                        f[each] = v[i]

    valueList = f.values()
    return max(valueList)

zltzlt

TJBEST 发表于 2020-2-12 17:19
您在试试这个，我尝试缩小了点空间

会超时

776667

from itertools import combinations

def fun329(s,v,c):
    dict_x = {}
    result = 0
    for i in range(len(v)):
        dict_x[c[i]] = v[i]
    for i in range(1,len(v)+1):
        for j in combinations(c,i):
            if sum(j) <= s and sum([dict_x[n] for n in j]) > result:
                result = sum([dict_x[n] for n in j])
    return result