[已解决]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)):

解答错误

输入：

1. s = 195387950,
   
2. v = [277996895,67034365,215265173,17927245,196665561,122553408,229181848,37953684,130611629,18096518,221937650,16569090,215131206,246680015,75894559,177999561,249070738,321264238,110845985,176753214],
   
3. 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 很大

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

1. def fun329(s,v,c):
   
2.     #0/1背包问题 由于 给的条件没有说 每个同体积同价值的个数（或无限） 只能按照0/1背包去算
   
3.     #采用循环遍历
   
4.     #s是容量 v是价值 c是体积
   
5.     M = len(v)
   
6.     f = {}
   
7.    
   
8.     for i in range(0,M):
   
9.         AList = list(f.keys())
   
10.         BList = list(map(lambda x:c[i] + x,AList))
    
11.         BList.append(c[i])
    
12.         keyList = sorted(set(AList + BList))
    
13.         keyList.reverse()
    
14.         for each in keyList:
    
15.             if each > s:
    
16.                 pass
    
17.             else:
    
18.                 if (each in AList) and (each in BList):
    
19.                     try:
    
20.                         f[each] = max([f[each],f[each - c[i]] + v[i]])
    
21.                     except Exception:
    
22.                         f[each] = max([f[each],v[i]])
    
23.                 elif (each in BList):
    
24.                     try:
    
25.                         f[each] = f[each - c[i]] + v[i]
    
26.                     except Exception:
    
27.                         f[each] = v[i]
    
28. 
    
29.     valueList = f.values()
    
30.     return max(valueList)

复制代码

zltzlt

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

会超时

776667

1. from itertools import combinations
   
2. 
   
3. def fun329(s,v,c):
   
4.     dict_x = {}
   
5.     result = 0
   
6.     for i in range(len(v)):
   
7.         dict_x[c[i]] = v[i]
   
8.     for i in range(1,len(v)+1):
   
9.         for j in combinations(c,i):
   
10.             if sum(j) <= s and sum([dict_x[n] for n in j]) > result:
    
11.                 result = sum([dict_x[n] for n in j])
    
12.     return result

复制代码