zltzlt 发表于 2020-2-12 13:53:33

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


超时

zltzlt 发表于 2020-2-12 14:21:33

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

输入大数据超出内存限制

zltzlt 发表于 2020-2-12 14:22:40

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


解答错误

输入：s = 195387950,
v = ,
s =
输出：690993069
预期结果：765577292

zltzlt 发表于 2020-2-12 14:26:30

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

超时

zltzlt 发表于 2020-2-12 14:27:10

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

60 ms

zltzlt 发表于 2020-2-12 14:28:05

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


会超时

zltzlt 发表于 2020-2-12 14:28:32

ouyunfu 发表于 2020-2-12 01:07
s = 10
v =
c =


https://fishc.com.cn/forum.php?mod=viewthread&tid=52272&extra=page%3D1%26filter%3Dtypeid%26typeid%3D441

zltzlt 发表于 2020-2-12 14:30:58

ouyunfu 发表于 2020-2-12 01:07
s = 10
v =
c =


会超时

zltzlt 发表于 2020-2-12 14:31:37

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

超出内存限制

zltzlt 发表于 2020-2-12 14:32:12

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

超时

坑得飞起 发表于 2020-2-12 14:47:54

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


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

fan1993423 发表于 2020-2-12 15:07:45

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

是不是只有我一个没有超时啊{:10_256:}

zltzlt 发表于 2020-2-12 15:08:42

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

是

TJBEST 发表于 2020-2-12 15:27:09

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

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

坑得飞起 发表于 2020-2-12 16:04:16

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

你的算法是什么？

zltzlt 发表于 2020-2-12 16:15:02

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

因为 n 很大

fan1993423 发表于 2020-2-12 16:16:34

本帖最后由 fan1993423 于 2020-2-12 16:19 编辑

坑得飞起 发表于 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重新回到初始值。{:10_256:}

TJBEST 发表于 2020-2-12 17:19:41

本帖最后由 TJBEST 于 2020-2-12 17:29 编辑

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 + x,AList))
      BList.append(c)
      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 = max(,f] + v])
                  except Exception:
                        f = max(,v])
                elif (each in BList):
                  try:
                        f = f] + v
                  except Exception:
                        f = v

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

zltzlt 发表于 2020-2-12 19:33:39

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

会超时{:10_266:}

776667 发表于 2020-10-21 11:00:55

from itertools import combinations

def fun329(s,v,c):
    dict_x = {}
    result = 0
    for i in range(len(v)):
      dict_x] = v
    for i in range(1,len(v)+1):
      for j in combinations(c,i):
            if sum(j) <= s and sum( for n in j]) > result:
                result = sum( for n in j])
    return result
页: 1 [2]
查看完整版本: Python：每日一题 329