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

zltzlt

动心成神 发表于 2019-10-28 23:08

输入 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

Unicorn# 发表于 2019-10-29 01: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

XiaoPaiShen 发表于 2019-10-29 04: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]
输出：4997
预期结果：5000

zltzlt

Stubborn 发表于 2019-10-29 06:39
时间有点超，先睡觉，起床再优化吧，结果验算了下，结果没有问题，楼上可能就问题了，顺便看看， ...

输入 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

kaohsing 发表于 2019-10-29 08:31

输入：m = 10, A = [3,4,8,5]
输出：12
预期结果：9

zltzlt

华一仙 发表于 2019-10-29 08:58

输入：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]
输出：4997
预期结果：5000

zltzlt

阴阳神万物主 发表于 2019-10-29 09:06
我写了个有局限性的函数，但目前没发现能让它出错的输入数据，所以我就发出来了：

因为我自己不是很确定 ...

输入 m = 111,
A = [446,242,400,308,858,680,290,597,418,552,810,890,452,374,425,412,490,732,397,231,138,923,204,163,685,406,134,530,814,776,115,827,902,75,875,756,570,648,420,420,883,788,254,251,189,551,917,451,637,897,867,391,272,447,709,346,371,503,886,566,985,460,78,330,581,256,182,345,278,137,912,170,233,707,652,1000,201,231,82,932,263,471,739,61,904,571,818,238,544,706,889,974,86,617,871,930,223,184,73,109,86,985,197,535,974,298,594,771,130,178,171,725,449,577,740,152,588,239,617,784,404,319,795,84,906,773,808,578,699,717,222,386,677,390,976,967,658,130,129,108,473,948,623,902,524,587,588,732,968,887,821,607,163,180,524,758,337,270,153,723,242,929,470,88,830,467,944,588,623,912,892,635,946,650,941,310,674,207,343,984,896,760,152,293,311,169,983,53,581,626,606,806,119,440,348,68,198,651,493,191,90,238,828,179,431,332,156,587,960,444,499,792,822,418,53,870,746,456,724,546,388,829,885,740,306,396,439,256,123,119,768,949,288,192,998,955,592,509,106,89,586,107,639,166,411,611,275,166,923,579,608,588,770,488,688,754,445,209,334,642,405,587,635,786,928,984,787,739,600,857,268,905,872,577,878,644,819,421,893,290,610,283,831,581,376,596,583,83,101,68,925,304,371,713,912,765,346,1000,489,990,978,865,791,202,937,855,886,496,654,590,336,63,588,233,86,917,220,928,221,655,465,818,595,968,81,791,289,866,454,986,852,742,377,94,787,74,992,388,973,621,451,83,849,947,480,862,393,938,746,685,69,669,537,907,714,899,705,408,743,595,846,408,942,375,263,804,695,777,253,317,820,939,915,619,916,796,887,76,588,843,847,408,612,563,733,864,882,398,953,882,635,980,779,882,145,476,605,424,304,265,565,474,73,1000,835,732,537,889,639,930,648,763,207,201,123,761,119,599,420,332,984,886,857,211,642,518,269,840,355,450,795,85,873,734,501,963,56,186,426,275,606,86,341,738,599,64,76,411,485,961,818,303,659,277,997,850,108,375,631,748,478,436,657,812,862,689,959,674,445,388,973,545,879,437,918,409,783,484,736,227,466,169,348,285,377,112,780,977,678,840,826,830,92,232,937,890,542,230,208,668,725,289,673,670,178,861,316,712,148,683,450,757,649,672,605,569,314,179,959,715,605,824,842,428,586,590,833,280,990,412,349,154,503,426,91,148,759,257,408,344,670,462,738,83,906,644,911,689,811,284,739,521,935,737,355,995,109,734,685,104,328,356,610,385,562,726,809,588,898,266,769,790,571,347,841,189,304,738,352,449,439,952,766,394,890,368,848,845,540,495,856,332,882,762,929,470,409,158,118,799,263,622,124,787,709,428,880,768,948,856,586,775,562,705,145,609,435,566,429,230,459,992,465,350,485,63,825,101,483,980,72,464,663,134,462,791,806,589,812,803,684,208,927,938,688,844,434,630,175,867,828,371,333,464,382,164,523,784,978,491,558,277,811,388,384,590,828,486,855,237,719,90,164,665,995,163,551,524,264,417,407,245,672,848,251,815,572,912,964,156,105,256,306,151,331,956,57,393,374,459,212,813,401,845,312,794,879,456,398,942,630,206,654,369,119,718,664,704,547,471,824,692,456,176,947,369,899,149,161,144,723,705,578,223,969,634,565,135,846,765,743,850,409,846,399,280,820,596,556,730,75,179,998,746,868,619,387,980,343,988,368,75,261,388,956,133,394,778,185,897,143,767,518,284]
输出：109
预期结果：110

zltzlt

战场原 发表于 2019-10-29 14:26
def solution(m:int, A: list) -> int :
    A.sort()
    res = set()

输入 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

findland 发表于 2019-10-29 15:02

输入 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

爱吃鱼的mao 发表于 2019-10-29 17:36

输入 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] 超时

Unicorn#

zltzlt 发表于 2019-10-29 20:50
输入 m = 5000，A = [828,125,740,724,983,321,773,678,841,842,875,377,674,144,340,467,625,916,463,92 ...

我这边运行没问题吖

zltzlt

Unicorn# 发表于 2019-10-29 21:05
我这边运行没问题吖

超出内存限制，请减少空间复杂度

danteer

这题想不超时还要算对也太狠了，稍微改进了一点，其他方法总感觉有漏洞还没想出来

1. import itertools
   
2. 
   
3. def func(m,A):
   
4.     A.sort()
   
5.     x = 0
   
6.     counter1 = -1
   
7.     for i in range(-1,-len(A)-1,-1):
   
8.         while x < m:
   
9.             x += A[i]
   
10.             counter1 += 1
    
11.         if x >= m:
    
12.             break
    
13.     y = 0
    
14.     counter2 = 0
    
15.     for each in A:
    
16.         y += each
    
17.         counter2 = counter2 + 1
    
18.         if y >= m:
    
19.             break
    
20.     list1 = []
    
21.     for i in range(counter1,counter2):
    
22.         temp = itertools.combinations(A,i)
    
23.         for each in temp:
    
24.             xx = 0
    
25.             for j in each:
    
26.                 xx += j
    
27.                 if xx >= m:
    
28.                     break
    
29.             list1.append(xx)
    
30.     result = list1[0]
    
31.     for each in list1:
    
32.         if each <= m:
    
33.             if m - each < m - result:
    
34.                 result = each
    
35.     return result

复制代码

zltzlt

danteer 发表于 2019-10-29 21:05
这题想不超时还要算对也太狠了，稍微改进了一点，其他方法总感觉有漏洞还没想出来

输入：m = 90, A = [12,3,7,4,5,13,2,8,4,7,6,5,7]
输出：81
预期结果：83

foxiangzun

利用背包问题来求解

这里虽然只有“重量”没有“价钱”，但是价钱也可以当做重量来看，所以这里就好办了，代码如下：

1. import numpy as np
   
2. 
   
3. def package2(weight, price, weight_most):
   
4.         resArr = np.zeros((weight_most) + 1, dtype=np.int32)
   
5.         lenth = len(weight)
   
6.         for i in range(0, lenth):
   
7.                 for j in range(weight_most, 0, -1):
   
8.                         if weight[i] <= j:
   
9.                                 resArr[j] = max(resArr[j], resArr[j - weight[i]] + price[i])
   
10.         return resArr[-1]
    
11. 
    
12. 
    
13. list1 = [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]
    
14. maxSize = 5000
    
15. print(package(list1, list1, maxSize))

复制代码

Unicorn#

zltzlt 发表于 2019-10-29 21:05
超出内存限制，请减少空间复杂度

根据经验规律优化了一点
感觉还能优化，先把这个发了看下行不行

1. def solve(m, A):
   
2.     A.sort()
   
3.     n = len(A) - 1
   
4.     record = {}
   
5.     def f(x, y):
   
6.         if (x, y) in record:
   
7.             t = record[(x, y)]
   
8.             del record[(x, y)]
   
9.             return t
   
10.         elif x == -1 or y == 0:
    
11.             return 0
    
12.         else:
    
13.             if y >= A[x]:
    
14.                 a = f(x-1, y-A[x]) + A[x]
    
15.             else:
    
16.                 a = -1
    
17.             b = f(x-1, y)
    
18.             t = max(a, b)
    
19.             record[(x, y)] = t
    
20.             return t
    
21.     print(f(n, m))

复制代码

阴阳神万物主

因为，发现了能让我那代码出错的输入数据，于是我改成了动态规划（可能不是），怕递归超出最大深度，于是我硬生生给改成了非递归的……
这回应该没有能让它出错的数据了，效率我感觉还行：

1. def load(m:int,A:'list')->int:
   
2.     tot = 0
   
3.     A.sort(reverse=True)#确定从大到小的顺序
   
4.     adds = []
   
5.     max_add =[]
   
6.     i = 0
   
7.     summ = 0
   
8.     while i < len(A):
   
9.         save = False
   
10.         #print('调试 比较',m-summ,A[i],i)
    
11.         if m-summ >= A[i]:#剩余空间足以放下该件物品
    
12.             summ += A[i]
    
13.             adds.append((A.pop(i),i))
    
14.             save = True
    
15.         if save:
    
16.             #该件物品已存放
    
17.             #print('调试 存放',m-summ,summ,i,len(A),[x[0] for x in adds])
    
18.             if summ == m:
    
19.                 print('验算吧！',[x[0] for x in adds])
    
20.                 return m
    
21.             elif summ > tot:
    
22.                 tot = summ
    
23.                 max_add = [x[0] for x in adds]
    
24.             if i < len(A):
    
25.                 continue#尝试下一件物品，已存放的被取出，后面的往前移，下标不变
    
26.         if i+1 < len(A):#还有小的东西
    
27.             i += 1
    
28.             #print('调试 下一位',summ,i,len(A),adds)
    
29.             continue
    
30.         while i+1 >= len(A) and adds:#没有更小的了,但是可以返回上一步
    
31.             quality,i = adds.pop()
    
32.             summ -= quality
    
33.             A.insert(i,quality)
    
34.             #print('调试 返回上一步',quality,summ,i,len(A),adds)
    
35.         else:
    
36.             if (not adds):#没有上一步
    
37.                 if i+1<len(A):#有更小的
    
38.                     i += 1
    
39.                     #print('调试 下一位',summ,i,len(A),adds)
    
40.                     continue
    
41.                 else:#没有更小的
    
42.                     #print('读条完了',i,A)
    
43.                     break#读条完了
    
44.             elif i+1 < len(A):#还有上一步，但出现了更小的
    
45.                 i += 1
    
46.                 continue
    
47.     #print('此时 adds中',[x[0] for x in adds])
    
48.     #print(i,A,adds)
    
49.     #print('验算吧！',max_add)
    
50.     return tot
    
51. 
    
52. if __name__ == '__main__':
    
53.     print('示例1 输出：',load(10,[3,4,8,5]))
    
54.     print('示例2 输出：',load(12,[2,3,5,7]))
    
55.     print('自测 死循环？',load(1,[2,3,4,5]))
    
56.     print('大数据？输出：',load(m = 20000, A = [828,125,740,724,983,321,773,
    
57.                                          678,841,842,875,377,674,144,340,467,
    
58.                                          625,916,463,922,255,662,692,123,778,
    
59.                                          766,254,559,480,483,904,60,305,966,
    
60.                                          872,935,626,691,832,998,508,657,215,
    
61.                                          162,858,179,869,674,452,158,520,138,
    
62.                                          847,452,764,995,600,568,92,496,533,
    
63.                                          404,186,345,304,420,181,73,547,281,
    
64.                                          374,376,454,438,553,929,140,298,451,
    
65.                                          674,91,531,685,862,446,262,477,573,
    
66.                                          627,624,814,103,294,388]*5))
    

复制代码

zltzlt

Unicorn# 发表于 2019-10-29 22:05
根据经验规律优化了一点
感觉还能优化，先把这个发了看下行不行

输入

1. m = 9000, A = [988,417,92,268,313,293,530,134,311,918,355,826,94,580,793,731,320,101,612,410,640,393,278,660,842,543,130,793,407,797,176,685,521,776,473,756,597,376,615,547,310,579,177,450,842,677,640,687,515,178,583,271,161,401,595,354,868,773,74,178,626,192,747,716,148,499,654,584,886,127,171,121,563,222,802,818,546,230,50,470,134,689,276,948,261,794,680,674,444,580,313,125,473,940,888,899,75,243,792,568,173,872,376,513,719,302,96,369,163,314,61,58,181,262,85,432,695,728,759,969,305,826,345,388,79,953,838,648,692,240,645,675,352,257,711,536,272,779,99,332,909,175,711,561,170,390,814,820,383,690,460,664,395,831,420,876,413,824,605,812,581,343,518,213,236,957,273,707,561,922,681,985,282,493,299,261,382,560,263,361,936,746,224,509,578,149,993,989,730,354,587,662,184,924,70,422,344,794,459,277,286,572,970,947,665,287,675,239,208,596,907,685,714,544,90,706,305,538,558,182,798,924,211,245,613,416,63,514,830,641,421,858,238,968,77,612,864,524,988,302,332,402,751,421,992,94,836,953,445,600,197,894,195,630,792,762,844,993,80,186,471,725,265,132,939,509,653,347,837,877,601,941,418,784,677,351,673,734,790,465,965,600,267,478,868,927,825,697,400,116,708,520,792,129,448,464,336,570,888,100,352,300,717,65,999,673,595,376,480,782,929,288,810,400,546,78,991,566,494,904,461,110,741,757,743,351,570,713,615,589,838,433,970,895,767,862,314,601,205,316,831,912,453,701,919,778,843,891,794,612,287,403,358,812,336,455,114,758,116,456,467,895,108,273,887,561,586,841,858,548,352,216,425,537,990,305,568,138,985,274,436,483,749,693,817,789,325,667,481,723,725,742,420,851,666,849,893,169,911,320,696,241,108,633,877,343,898,690,986,721,819,160,238,780,185,143,473,208,506,829,747,640,407,734,84,724,873,492,798,839,161,141,696,571,688,866,111,795,651,983,664,748,875,814,710,556,219,72,462,948,89,114,497,176,68,409,826,181,118,781,394,123,644,149,665,739,381,912,256,693,752,810,697,50,739,315,219,930,411,453,362,845,609,485,461,920,290,815,283,778,635,787,154,987,404,60,414,462,919,864,356,124,169,133,586,242,302,428,68,517,576,300,432,203,228,932,657,916,997,852,197,625,157,603,475,937,215,710,234,645,281,569,645,912,390,361,853,661,981,290,303,303,342,215,716,136,293,579,555,197,299,969,619,279,696,820,374,748,521,788,482,538,896,600,574,189,318,857,125,752,190,104,987,617,531,929,602,423,242,328,461,780,409,474,903,675,388,625,80,230,500,653,546,990,138,576,888,481,402,487,948,226,441,431,145,765,222,933,276,182,769,228,91,935,728,385,543,466,415,574,227,319,572,752,759,239,724,956,709,861,512,157,294,950,265,741,373,498,767,1000,957,168,149,668,811,573,658,971,711,662,352,473,404,868,750,793,614,532,853,620,918,283,301,547,221,486,164,664,275,287,360,79,680,59,461,874,283,438,512,358,378,559,378,681,841,479,454,513,419,310]

复制代码

超时

zltzlt

foxiangzun 发表于 2019-10-29 21:28
利用背包问题来求解

这里虽然只有“重量”没有“价钱”，但是价钱也可以当做重量来看，所以这里就好办了 ...

注意：在答题代码中不能使用第三方库。

阴阳神万物主

zltzlt 发表于 2019-10-29 20:59
输入 m = 111,
A = [446,242,400,308,858,680,290,597,418,552,810,890,452,374,425,412,490,732,397 ...

代码已经修改，自测这一测试数据已可正确输出
那层楼