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

zltzlt

阴阳神万物主 发表于 2019-10-30 20:23
打听打听，这题，时间限制是多久啊

这个保密，你可以参考通过的代码

阴阳神万物主

zltzlt 发表于 2019-10-30 20:24
这个保密，你可以参考通过的代码

好伐，大约 11 秒？

Unicorn#

zltzlt 发表于 2019-10-30 20:03
测试了这么多答题代码，只有一个是通过的

https://fishc.com.cn/forum.php?mod=redirect&goto=findpos ...

呐
居然忘了 用循环而不是递归来实现DP 会更优
厉害厉害

Unicorn#

jdzzj 发表于 2019-10-30 16:47

厉害了厉害了
内层的那个循环是真的秀
学到了

阴阳神万物主

Unicorn# 发表于 2019-10-30 20:34
厉害了厉害了
内层的那个循环是真的秀
学到了

呐，你可以去看看我的最初版本，我只要去除掉一个判断语句，从逻辑上讲，跟他的代码一样

阴阳神万物主

zltzlt 发表于 2019-10-30 20:24
这个保密，你可以参考通过的代码

恩姆，版主大大，请问：您是使用的什么样的方法测试代码用时的呢？


P.S. 我在代码中添加了测试时间的代码，然后就发现了，用时都是没超过 1s 即 1000ms 的啊

zltzlt

阴阳神万物主 发表于 2019-10-30 20:56
恩姆，版主大大，请问：您是使用的什么样的方法测试代码用时的呢？

拿几个很大的数测试

阴阳神万物主

zltzlt 发表于 2019-10-30 21:01
拿几个很大的数测试

超级大的数据，可以麻烦传上来吗？我想看看在真正的大数据面前，我的最初版删掉一个判断语句后，和我改了老半天才整出来的也许是动态规划的代码，到底有什么区别
好吧……我自己把您贴出来过的某部分测试数据，m 减小或不变，A直接在后面乘以一个较大的数，然后就……高下立判啊！

Stubborn

阴阳神万物主 发表于 2019-10-30 21:14
超级大的数据，可以麻烦传上来吗？我想看看在真正的大数据面前，我的最初版删掉一个判断语句后，和我改了 ...

我后面的就是动态规划，别整，，没地找运维要内存去create数组

阴阳神万物主

Stubborn 发表于 2019-10-30 21:39
我后面的就是动态规划，别整，，没地找运维要内存去create数组

放心，我那个，所有的数组存放的元素总量，最多是输入列表的两倍

Stubborn

阴阳神万物主 发表于 2019-10-30 21:44
放心，我那个，所有的数组存放的元素总量，最多是输入列表的两倍

修改过，修剪下，没啥毛病了，不知道哪里测呀～

1. def solve(P:int, W:list):
   
2. 
   
3.     if sum(W) < P:
   
4.         return sum(W)
   
5. 
   
6.     solves_dic = dict()
   
7.     new_W = []
   
8. 
   
9.     for index,value in enumerate(W):
   
10.         # 一次清理，单个值不能被放入剔除
    
11.         if P > value:
    
12.             new_W.append(value)
    
13.             solves_dic[P - value] = {index,}
    
14. 
    
15.     W = new_W
    
16.     W.sort()
    
17.     length = len(W)
    
18.     result,index = P,[]
    
19. 
    
20.     for i in range(length): # W[i]件物品
    
21.         cp = solves_dic.copy()
    
22.         for key, value in cp.items():
    
23.             # W[i]件物品已经被装载
    
24.             if i in value:
    
25.                 continue
    
26.             # W[i]件物品可以被装载
    
27.             res = key - W[i]
    
28.             # 背包刚好被装满，可以结束
    
29.             if res == 0:
    
30.                 return P
    
31.             elif res > 0:
    
32.                 var = value.copy()
    
33.                 var.add(i)
    
34.                 solves_dic[res] = var
    
35.             # W[i]件物品不能被装载,记录结果，因为W被排序，W[i]不能被放进，i件后面都讲不能进入,并且被清理
    
36.             else:
    
37.                 if key < result:
    
38.                     result, index = key,value
    
39.                 del solves_dic[key]
    
40. 
    
41.     return P-result

复制代码

阴阳神万物主

Stubborn 发表于 2019-10-31 02:40
修改过，修剪下，没啥毛病了，不知道哪里测呀～

在代码的最后，加上：

1. import time
   
2. st = time.perf_counter()
   
3. #这里调用函数
   
4. ed = time.perf_counter()
   
5. print('调用前： %f 调用后：%f 用时：%f'%(st,ed,ed-st))

复制代码

ed-st 就是其中调用某函数的用时，单位是秒

Stubborn

阴阳神万物主 发表于 2019-10-31 10:17
在代码的最后，加上：
ed-st 就是其中调用某函数的用时，单位是秒

38 楼 m=9000  0.4  测试发现，包大，时间会比较久，数据里在基础上*10 结果都是1s1, 包*2   *3 结果就拉稀