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

zltzlt

阴阳神万物主 发表于 2019-10-29 22:20
代码已经修改，自测这一测试数据已可正确输出
那层楼

OK，现在在手机上不方便测试，明天再测试吧

Unicorn#

zltzlt 发表于 2019-10-29 22:14
输入  超时

...............................................

自闭中

华一仙

1. def f265(m, A):        
   
2.     lst = [0] * (m+1)
   
3.     for i in range(len(A)):
   
4.         for j in range(m, 0, -1):
   
5.             if A[i] <= j and lst[j] <= lst[j-A[i]] + A[i]:
   
6.                 lst[j] = lst[j-A[i]] + A[i]
   
7.     return lst[m]

复制代码

foxiangzun

zltzlt 发表于 2019-10-29 22:14
注意：在答题代码中不能使用第三方库。

修改了第三方库的使用，现在用原生列表处理，代码如下：

1. def package(weight, weight_most):
   
2.         weight.sort()
   
3.         lenth = len(weight)
   
4.         resultList = [0 for i in range(weight_most + 1)]
   
5.         for i in range(lenth) :
   
6.                 for j in range(weight_most, 0, -1) :
   
7.                         if weight[i] <= j :
   
8.                                 resultList[j] = max(resultList[j], resultList[j - weight[i]] + weight[i])
   
9.         return resultList[-1]

复制代码

Python3005

1. def bag(m , A):
   
2.         value = []
   
3.         for n in range(2, len(A)+1):
   
4.                 p = i.combinations(A, n)
   
5.                 for each in p:
   
6.                         if sum(each) > m:
   
7.                                 continue
   
8.                         else:
   
9.                                 value.append(sum(each))
   
10.         value.sort()
    
11.         return value[-1]

复制代码

Stubborn

1. def Optimal(m,A):
   
2.     length = len(A)
   
3.     backing = [[0 * _ for _ in range(m+1)] for _ in range(length+1)]
   
4.     max_number = 0
   
5. 
   
6.     for j in range(length): # 每件物品 A[i]
   
7.         for i in range(m+1):  # 背包的容量:最后
   
8.             if i >= A[j]:
   
9.                 backing[j + 1][i] = backing[j][i - A[j]] + A[j]
   
10.                
    
11.                 if backing[j + 1][i] == m:
    
12.                     return m
    
13.                 if backing[j + 1][i] > max_number:
    
14.                     max_number = backing[j + 1][i]
    
15.             else:
    
16.                   backing[j + 1][i] = max(backing[j][i],backing[j+1][i])
    
17. 
    
18.     return max_number

复制代码

python万

findland

V2.0
穷举，感觉好蠢

1. def package_1(A):
   
2.    
   
3.     for j in range(2**len(A)):
   
4.         tmp = j
   
5.         total=0
   
6.         count=0
   
7.         while tmp!=0:
   
8.             total+=A[count]*(tmp%2)
   
9.             tmp=tmp//2
   
10.             count+=1
    
11.         yield total
    
12. def get_max(A,m):
    
13.     res=0
    
14.    
    
15.     for i in (package_1(A)):
    
16.         if m>=i>res:
    
17.             res=i
    
18.     return res
    
19. m, A = 5000, [828,125,740,724,983,321,773,678,841,842,875,377,674,144,340,467,625,916,463,922,255,662,692,123,778,766,254,559,480,483,904,60,305,966,872,935,626,691,832,998,508,657,215,162,858,179,869,674,452,158,520,138,847,452,764,995,600,568,92,496,533,404,186,345,304,420,181,73,547,281,374,376,454,438,553,929,140,298,451,674,91,531,685,862,446,262,477,573,627,624,814,103,294,388]
    
20. 
    
21. test=get_max(A,m)
    
22. print(test)

复制代码

jerryxjr1220

提供一个思路“广度优先搜索策略”，因为有上限限制，所以其实广度并不需要全列举，超过上限的就剪枝，速度还是非常快的：
假如表A = [a,b,c,d] 上限是U
建立一个字典cans = {}，把A中的所有项都放进去，键是值的和。
然后依次从表A中取出每一个放入字典中去求和，看是否超过上限，没超就加上，超过就舍弃，循环一遍就出来了。
我手头没有python，用aardio临时写了一下

1. import console;
   
2. console.open();
   
3. limit = 5000;
   
4. A = "828,125,740,724,983,321,773,678,841,842,875,377,674,144,340,467,625,916,463,922,255,662,692,123,778,766,254,559,480,483,904,60,305,966,872,935,626,691,832,998,508,657,215,162,858,179,869,674,452,158,520,138,847,452,764,995,600,568,92,496,533,404,186,345,304,420,181,73,547,281,374,376,454,438,553,929,140,298,451,674,91,531,685,862,446,262,477,573,627,624,814,103,294,388"
   
5. A = string.split(A,",");
   
6. list = {}
   
7. cans = {}
   
8. for _,i in A{
   
9.         n = tonumber(i);
   
10.         table.push(list,n);
    
11.         cans[n] = {n}
    
12. }
    
13. 
    
14. for _,ea in list {
    
15.         for ei,ec in cans {
    
16.                 if ei == ea continue ;
    
17.                 if table.find(ec,ea) continue ;
    
18.                 if ea+ei>limit continue ;
    
19.                 new = table.clone(ec);
    
20.                 table.push(new,ea);
    
21.                 cans[ea+ei] = new;
    
22.         }
    
23. }
    
24. 
    
25. s = ""
    
26. for k,v in cans{
    
27.         //console.log(k);
    
28.         //console.log(table.unpack(v));
    
29.         s ++= tostring(k) ++ '\r\n';
    
30.         for _,i in v {
    
31.                 s ++= tostring(i) ++ '\t';
    
32.         }
    
33.         s ++= '\r\n';
    
34. }
    
35. 
    
36. console.log(s)
    
37. 
    
38. string.save("temp.txt", s)
    
39. 
    
40. console.pause(true);

复制代码

结果：
5000
144        138        92        547        281        438        553        674        531        685        814        103       

jdzzj

1. def fun265(self, m, A):
   
2.       
   
3.     A.sort(reverse=True)
   
4.         
   
5.     sizes=[]
   
6.         
   
7.     for i in range(len(A)):
   
8.         size=0
   
9.         B=A[i:]
   
10.            
    
11.         for j in range(len(B)):
    
12.                
    
13.             size+=B[j]
    
14.             if size>m:
    
15.                 size-=B[j]
    
16.                 continue
    
17.             
    
18.         sizes.append(size)
    
19.             
    
20.     return max(sizes)

复制代码

zltzlt

阴阳神万物主 发表于 2019-10-29 22:08
因为，发现了能让我那代码出错的输入数据，于是我改成了动态规划（可能不是），怕递归超出最大深度，于是我 ...

还是会超时……

zltzlt

华一仙 发表于 2019-10-29 23:38

恭喜通过！写的真简洁

执行用时：10053 ms

Unicorn#

zltzlt 发表于 2019-10-29 22:14
输入  超时

emmm
DP + 记忆化搜索都会超时...
暂时没办法辽

zltzlt

Unicorn# 发表于 2019-10-30 20:02
emmm
DP + 记忆化搜索都会超时...
暂时没办法辽

测试了这么多答题代码，只有一个是通过的

https://fishc.com.cn/forum.php?m ... 147&ptid=149610

zltzlt

foxiangzun 发表于 2019-10-30 00:32
修改了第三方库的使用，现在用原生列表处理，代码如下：

恭喜通过！

执行用时：10896 ms

zltzlt

Python3005 发表于 2019-10-30 03:00

输入 m = 5000, A = [828,125,740,724,983,321,773,678,841,842,875,377,674,144,340,467,625,916,463,922,255,662,692,123,778,766,254,559,480,483,904,60,305,966,872,935,626,691,832,998,508,657,215,162,858,179,869,674,452,158,520,138,847,452,764,995,600,568,92,496,533,404,186,345,304,420,181,73,547,281,374,376,454,438,553,929,140,298,451,674,91,531,685,862,446,262,477,573,627,624,814,103,294,388] 超出内存限制

zltzlt

Stubborn 发表于 2019-10-30 07:09

输入 m = 80000, A = [81,112,609,341,164,601,97,709,944,828,627,730,460,523,643,901,602,508,401,442,738,443,555,471,97,644,184,964,418,492,920,897,99,711,916,178,189,202,72,692,86,716,588,297,512,605,209,100,107,938,246,251,921,767,825,133,465,224,807,455,179,436,201,842,325,694,132,891,973,107,284,203,272,538,137,248,329,234,175,108,745,708,453,101,823,937,639,485,524,660,873,367,153,191,756,162,50,267,166,996,552,675,383,615,985,339,868,393,178,932] 超出内存限制

zltzlt

findland 发表于 2019-10-30 11:56
V2.0
穷举，感觉好蠢

超时……

zltzlt

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

恭喜通过！

执行用时：201 ms

冠军宝座非你莫属

阴阳神万物主

zltzlt 发表于 2019-10-30 20:00
还是会超时……

打听打听，这题，时间限制是多久啊