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

zltzlt

今天的题目：

在 n 个物品中挑选若干物品装入背包，假设背包的大小为 m，每个物品的大小为 A[j]（所有物品大小的列表为 A），最多能装多满？

示例 1:

输入:  m = 10, A = [3, 4, 8, 5]
输出:  9

示例 2:

输入:  m = 12, A = [2,3,5,7]
输出:  12

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

jdzzj

2019-10-30 16:47:40

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)

复制代码

跳转到最佳答案楼层

Unicorn#

来啦

1. def solve(m, A):
   
2.     n = len(A) - 1
   
3.     def f(x, y):
   
4.         if x == 0 or y == 0:
   
5.             return 0
   
6.         else:
   
7.             a = f(x-1, y-A[x]) + A[x] if y >= A[x] else -1
   
8.             b = f(x-1, y)
   
9.             return max(a, b)
   
10.     print(f(n, m))

复制代码

zltzlt

Unicorn# 发表于 2019-10-28 21:03
来啦

解答错误

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

Unicorn#

不好意思 一点点错

1. def solve(m, A):
   
2.     n = len(A) - 1
   
3.     def f(x, y):
   
4.         if x == -1 or y == 0:
   
5.             return 0
   
6.         else:
   
7.             a = f(x-1, y-A[x]) + A[x] if y >= A[x] else -1
   
8.             b = f(x-1, y)
   
9.             return max(a, b)
   
10.     print(f(n, m))

复制代码

danteer

1. import itertools
   
2. 
   
3. def func(m,A):
   
4.     A.sort
   
5.     if A[0] > m:
   
6.         return None
   
7.     else:
   
8.         list1 = []
   
9.         for i in range(1,len(A)+1):
   
10.             temp = itertools.combinations(A,i)
    
11.             for each in temp:
    
12.                 x = 0
    
13.                 for j in each:
    
14.                     x += j
    
15.                 list1.append(x)
    
16.         result = list1[0]
    
17.         for each in list1:
    
18.             if each <= m:
    
19.                 if m - each < m - result:
    
20.                     result = each
    
21.         return result

复制代码

zltzlt

Unicorn# 发表于 2019-10-28 21:19
不好意思 一点点错

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

danteer 发表于 2019-10-28 21:50

A.sort()

帮你改正了

输入 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] 超出内存限制

动心成神

1. from itertools import combinations
   
2. 
   
3. def max_load(size,goods):
   
4.     # 求物品的组合情况
   
5.     con_goods = goods.copy()
   
6.     for i in range(2,len(goods)+1):
   
7.         goods_new = map(sum,combinations(goods,i))
   
8.         con_goods.extend(goods_new)
   
9. 
   
10.     # 取最大装载数
    
11.     while True:
    
12.         if size in con_goods:
    
13.             return size
    
14.         else:
    
15.             size -= 1
    
16. 
    
17. print(max_load(12,[2,3,5,7]))
    

复制代码

Unicorn#

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

DP都会超时.....难搞
我再优化试试

Unicorn#

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

添加了记忆化搜索，的确快很多了
递归重复次数太多了
是个狠人

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

复制代码

XiaoPaiShen

1. class Backpack:
   
2. 
   
3.     def calc(self, m, A):
   
4.         p = [[0 for _ in range(m+1)] for _ in range(len(A))]
   
5. 
   
6.         for i in range(len(A)):
   
7.             for j in range(m, 0, -1):
   
8.                 if i == 0:
   
9.                     if j >= A[i]:
   
10.                         p[i][j] = p[i][j-A[i]] + A[i]
    
11.                 elif j >= A[i]:
    
12.                     p[i][j] = p[i-1][j-A[i]] + A[i]
    
13.                 else:
    
14.                     p[i][j] = max(p[i][j],p[i-1][j])
    
15. 
    
16.         return p[len(A)-1][m]
    
17. 
    
18. if __name__ == '__main__':
    
19. 
    
20.     bp = Backpack()
    
21.     m, A = 90, [12,3,7,4,5,13,2,8,4,7,6,5,7]
    
22.    
    
23.     result = bp.calc(m, A)
    
24.     print(result)

复制代码

Stubborn

时间有点超，先睡觉，起床再优化吧，结果验算了下，结果没有问题，楼上可能就问题了，顺便看看，是哪里的耗时了

1. 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]
   
2. 
   
3. import copy
   
4. def solve(m, A):
   
5. 
   
6.     result = set()
   
7. 
   
8.     S_dict = {}
   
9.     for a, b in enumerate(A):
   
10.         S_dict[m - b] = [a,]
    
11. 
    
12.     def _n(m:int, value:list):
    
13.         for a,b in enumerate(A):
    
14.             if a in value:
    
15.                 continue
    
16.             if m - b >= 0:
    
17.                 var = copy.copy(value)
    
18.                 var.append(a)
    
19.                 try:
    
20.                     result.add(m-b)
    
21.                     S_dict[m-b] = S_dict.pop(m)
    
22.                 except KeyError:
    
23.                     S_dict[m - b] = var
    
24.                     continue
    
25.                 S_dict[m-b] = var
    
26. 
    
27.         return copy.copy(S_dict)
    
28. 
    
29.     a = len(A)
    
30.     for _ in range(a):
    
31.         s = copy.copy(S_dict)
    
32.         for key,value in s.items():
    
33.             _n(key, value)
    
34.     return m - min(result), S_dict.get(0, None)
    
35. 
    
36. print(solve(m,A))
    
37. 
    
38. (5000, [91, 80, 31, 67, 1, 58, 23, 51, 13, 49, 45, 92, 76, 43, 66, 85, 62, 26, 20, 42, 5, 32, 63, 77, 59])

复制代码

###################################有毒，躺下思索下，觉得很多地方不用判，下面是修改版，基本是秒出了###############################

1. import copy
   
2. def solve(m, A):
   
3. 
   
4.     A.sort()
   
5.     result,index =set(),0
   
6.     min_A = min(A)
   
7. 
   
8. 
   
9. 
   
10.     S_dict = {}
    
11.     for a, b in enumerate(A):
    
12.         S_dict[m - b] = [a,]
    
13. 
    
14.     def _n(m:int, value:list):
    
15.         for a,b in enumerate(A):
    
16.             if m < min_A or m - b < 0:
    
17.                 break
    
18.             elif a in value:
    
19.                 continue
    
20.             elif m - b > 0:
    
21.                 var = copy.copy(value)
    
22.                 var.append(a)
    
23.                 try:
    
24.                     result.add(m-b)
    
25.                     S_dict[m-b] = S_dict.pop(m)
    
26.                 except KeyError:
    
27.                     pass
    
28.                 S_dict[m-b] = var
    
29.             else:
    
30.                 return True
    
31. 
    
32.     a = len(A)
    
33.     for _ in range(a):
    
34.         s = copy.copy(S_dict)
    
35.         for key,value in s.items():
    
36.             if _n(key,value):
    
37.                 return m
    
38.     return m - min(result), S_dict.get(min(result), None)

复制代码

kaohsing

1. from itertools import combinations
   
2. 
   
3. 
   
4. def kao(val, lst):
   
5.     lst.sort()
   
6.     l = []
   
7.     if lst[0] > val:
   
8.         return False
   
9.     for i in range(2, len(lst) + 1):
   
10.         for j in combinations(lst, i):
    
11.             l.append(sum(j))
    
12.     if val in l:
    
13.         return val
    
14.     else:
    
15.         return Search(list(set(l)), val)
    
16. 
    
17. 
    
18. def Search(lst, val):
    
19.     lst.sort()
    
20.     low = 0
    
21.     height = len(lst)
    
22.     while low < height:
    
23.         mid = int((low + height) / 2)
    
24.         if lst[mid] < val:
    
25.             low = mid + 1
    
26.         elif lst[mid] > val:
    
27.             return lst[mid - 1]
    
28. 
    
29. 
    
30. print(kao(16, [2, 3, 5, 7]))

复制代码

华一仙

1. def f265(m, A):
   
2.     lst, tmp_lst = [0] * (m + 1), [0] * (m + 1)
   
3.     for raw in range(len(A)):
   
4.         for col in range(1, m+1):
   
5.             if col < A[raw]:
   
6.                 tmp_lst[col] = lst[col]
   
7.             else:
   
8.                 tmp_lst[col] = max(lst[col-A[raw]] + A[raw], lst[col-A[raw]])
   
9.         lst = tmp_lst[:]
   
10. 
    
11.     return lst[-1]

复制代码

阴阳神万物主

我写了个有局限性的函数，但目前没发现能让它出错的输入数据，所以我就发出来了：

1. def load(m:int,A:'list')->int:
   
2.     tot = 0
   
3.     A.sort(reverse=True)#确定从大到小的顺序
   
4.     length = len(A)
   
5.     for i in range(length):#左边界渐渐向右逼近
   
6.         sums = 0
   
7.         for j in A[i:]:
   
8.             sums += j
   
9.             if sums == m:#背包能够被装满，直接输出背包容量
   
10.                 return m
    
11.             elif m > sums > tot:#在不超过背包容量的前提下，尽可能的装载
    
12.                 tot = sums
    
13.             elif sums > m:#装了这个大件就超过了容量，所以不装
    
14.                 sums -= j
    
15.         if sums < tot:#无法再创新高
    
16.             break
    
17.     return tot
    
18. 
    
19. if __name__ == '__main__':
    
20.     print('示例1 输出：',load(10,[3,4,8,5]))
    
21.     print('示例2 输出：',load(12,[2,3,5,7]))
    
22.     print('大数据？输出：',load(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]))
    

复制代码

因为我自己不是很确定，所以稍微改了改，让输出包含了最多能装的、和怎么装能装这么多

1. def load(m:int,A:'list')->tuple:
   
2.     tot = 0
   
3.     who = []
   
4.     A.sort(reverse=True)#确定从大到小的顺序
   
5.     length = len(A)
   
6.     for i in range(length):#左边界渐渐向右逼近
   
7.         sums = 0
   
8.         adds = []
   
9.         for j in A[i:]:
   
10.             sums += j
    
11.             adds.append(j)
    
12.             if sums == m:#背包能够被装满，直接输出背包容量
    
13.                 return (m,adds)
    
14.             elif m > sums > tot:#在不超过背包容量的前提下，尽可能的装载
    
15.                 tot = sums
    
16.                 who = adds
    
17.             elif sums > m:#装了这个大件就超过了容量，所以不装
    
18.                 sums -= j
    
19.                 adds.pop()
    
20.         if sums < tot:#无法再创新高
    
21.             break
    
22.     return (tot,who)
    
23. 
    
24. if __name__ == '__main__':
    
25.     print('示例1 输出：',load(10,[3,4,8,5]))
    
26.     print('示例2 输出：',load(12,[2,3,5,7]))
    
27.     print('大数据？输出：',load(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]))
    

复制代码

战场原

def solution(m:int, A: list) -> int :
    A.sort()
    res = set()
    s = 0
    dfs(m, A, res, s)
    return max(res)

def dfs(m:int, A:list, res:set, s:int):
    if not A:
        res.add(s)
        return
    for i,v in enumerate(A):
        if v>m:
            res.add(s)
            return
        else:
            dfs(m-v, A[i+1:],res,s+v)
应该会超时...后面用dp改下

findland

1. def package(A,m):
   
2.     res=0
   
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.         if m>=total >res:
    
12.             res=total
    
13.     return res

复制代码

Stubborn

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

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

不知道是不是我验算有问题还是啥

1. m, A = 10000, [828, 125, 740, 724, {:10_266:}983, 321, 773, 678, 841, 842, 875, 377, 674, 144, 340, 467, 625, 916, 463, 922, 255,
   
2.                662, 692, 123, 778, 766, 254, 559, 480, 483, 904, 60, 305, 966, 872, 935, 626, 691, 832, 998, 508, 657,
   
3.                215, 162, 858, 179, 869, 674, 452, 158, 520, 138, 847, 452, 764, 995, 600, 568, 92, 496, 533, 404, 186,
   
4.                345, 304, 420, 181, 73, 547, 281, 374, 376, 454, 438, 553, 929, 140, 298, 451, 674, 91, 531, 685, 862,
   
5.                446, 262, 477, 573, 627, 624, 814, 103, 294, 388] * 2
   
6. 
   
7. 
   
8. (9997, [995, 983, 983, 966, 966, 935, 935, 929, 929, 922, 454])
   
9. 
   
10. 我运算，就是速度台太行了：(10000,[998, 995, 995, 983, 983, 966, 966, 935, 929, 321, 929])
    
11. 
    
12. A = 20000， m = m * 5
    
13. 
    
14. (19992, [998, 998, 998, 998, 995, 995, 995, 995, 995, 983, 983, 983, 983, 983, 966, 966, 966, 966, 966, 935, 345])
    
15. 
    
16. 我运算，就是速度台太行了：(20000,[998, 998, 998, 998, 995, 995, 995, 995, 995, 983, 983, 983, 983, 983, 966, 966, 966, 966, 998, 321, 935])
    

复制代码

爱吃鱼的mao

1. def function(m:int, a:list):
   
2.     a.sort(reverse=True)
   
3.     res = 0
   
4.     for i in range(len(a)):
   
5.         add = a[i]
   
6.         b = a[i+1:]
   
7.         while add <= m:
   
8.             for j in range(len(b)):
   
9.                 if b[j] <= m - add:
   
10.                     add += b[j]
    
11.                     b = b[j+1:]
    
12.                     break
    
13.             else:
    
14.                 break
    
15.         #print(add)
    
16.         if add > res:
    
17.             res = add
    
18.     return res

复制代码

阴阳神万物主

Stubborn 发表于 2019-10-29 16:33
不知道是不是我验算有问题还是啥

所以，这种的就是我的代码的局限所在。我等会儿再改。
话说， 12. 行那里是不是漏了个滑稽？