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

 def fun265(self, m, A):

      

    A.sort(reverse=True)

        

    sizes=[]

        

    for i in range(len(A)):

        size=0

        B=A[i:]

           

        for j in range(len(B)):

                

            size+=B[zxsq-anti-bbcode-j]

            if size>m:

                size-=B[zxsq-anti-bbcode-j]

                continue

            

        sizes.append(size)

            

    return max(sizes)

跳转到最佳答案楼层

Unicorn#

来啦

def solve(m, A):
    n = len(A) - 1
    def f(x, y):
        if x == 0 or y == 0:
            return 0
        else:
            a = f(x-1, y-A[x]) + A[x] if y >= A[x] else -1
            b = f(x-1, y)
            return max(a, b)
    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#

不好意思 一点点错

def solve(m, A):
    n = len(A) - 1
    def f(x, y):
        if x == -1 or y == 0:
            return 0
        else:
            a = f(x-1, y-A[x]) + A[x] if y >= A[x] else -1
            b = f(x-1, y)
            return max(a, b)
    print(f(n, m))

danteer

import itertools

def func(m,A):
    A.sort
    if A[0] > m:
        return None
    else:
        list1 = []
        for i in range(1,len(A)+1):
            temp = itertools.combinations(A,i)
            for each in temp:
                x = 0
                for j in each:
                    x += j
                list1.append(x)
        result = list1[0]
        for each in list1:
            if each <= m:
                if m - each < m - result:
                    result = each
        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] 超出内存限制

动心成神

from itertools import combinations

def max_load(size,goods):
    # 求物品的组合情况
    con_goods = goods.copy()
    for i in range(2,len(goods)+1):
        goods_new = map(sum,combinations(goods,i))
        con_goods.extend(goods_new)

    # 取最大装载数
    while True:
        if size in con_goods:
            return size
        else:
            size -= 1

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, ...

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

def solve(m, A):
    n = len(A) - 1
    record = {}
    def f(x, y):
        if (x, y) in record:
            return record[(x, y)]
        elif x == -1 or y == 0:
            record[(x, y)] = 0
            return 0
        else:
            if y >= A[x]:
                a = f(x-1, y-A[x]) + A[x]
            else:
                a = -1
            b = f(x-1, y)
            t = max(a, b)
            record[(x, y)] = t
            return t
    print(f(n, m))

XiaoPaiShen

class Backpack:

    def calc(self, m, A):
        p = [[0 for _ in range(m+1)] for _ in range(len(A))]

        for i in range(len(A)):
            for j in range(m, 0, -1):
                if i == 0:
                    if j >= A[i]:
                        p[i][j] = p[i][j-A[i]] + A[i]
                elif j >= A[i]:
                    p[i][j] = p[i-1][j-A[i]] + A[i]
                else:
                    p[i][j] = max(p[i][j],p[i-1][j])

        return p[len(A)-1][m]

if __name__ == '__main__':

    bp = Backpack()
    m, A = 90, [12,3,7,4,5,13,2,8,4,7,6,5,7]
    
    result = bp.calc(m, A)
    print(result)

Stubborn

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

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]

import copy
def solve(m, A):

    result = set()

    S_dict = {}
    for a, b in enumerate(A):
        S_dict[m - b] = [a,]

    def _n(m:int, value:list):
        for a,b in enumerate(A):
            if a in value:
                continue
            if m - b >= 0:
                var = copy.copy(value)
                var.append(a)
                try:
                    result.add(m-b)
                    S_dict[m-b] = S_dict.pop(m)
                except KeyError:
                    S_dict[m - b] = var
                    continue
                S_dict[m-b] = var

        return copy.copy(S_dict)

    a = len(A)
    for _ in range(a):
        s = copy.copy(S_dict)
        for key,value in s.items():
            _n(key, value)
    return m - min(result), S_dict.get(0, None)

print(solve(m,A))

(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])

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

import copy
def solve(m, A):

    A.sort()
    result,index =set(),0
    min_A = min(A)



    S_dict = {}
    for a, b in enumerate(A):
        S_dict[m - b] = [a,]

    def _n(m:int, value:list):
        for a,b in enumerate(A):
            if m < min_A or m - b < 0:
                break
            elif a in value:
                continue
            elif m - b > 0:
                var = copy.copy(value)
                var.append(a)
                try:
                    result.add(m-b)
                    S_dict[m-b] = S_dict.pop(m)
                except KeyError:
                    pass
                S_dict[m-b] = var
            else:
                return True

    a = len(A)
    for _ in range(a):
        s = copy.copy(S_dict)
        for key,value in s.items():
            if _n(key,value):
                return m
    return m - min(result), S_dict.get(min(result), None)

kaohsing

from itertools import combinations


def kao(val, lst):
    lst.sort()
    l = []
    if lst[0] > val:
        return False
    for i in range(2, len(lst) + 1):
        for j in combinations(lst, i):
            l.append(sum(j))
    if val in l:
        return val
    else:
        return Search(list(set(l)), val)


def Search(lst, val):
    lst.sort()
    low = 0
    height = len(lst)
    while low < height:
        mid = int((low + height) / 2)
        if lst[mid] < val:
            low = mid + 1
        elif lst[mid] > val:
            return lst[mid - 1]


print(kao(16, [2, 3, 5, 7]))

华一仙

def f265(m, A):
    lst, tmp_lst = [0] * (m + 1), [0] * (m + 1)
    for raw in range(len(A)):
        for col in range(1, m+1):
            if col < A[raw]:
                tmp_lst[col] = lst[col]
            else:
                tmp_lst[col] = max(lst[col-A[raw]] + A[raw], lst[col-A[raw]])
        lst = tmp_lst[:]

    return lst[-1]

阴阳神万物主

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

def load(m:int,A:'list')->int:
    tot = 0
    A.sort(reverse=True)#确定从大到小的顺序
    length = len(A)
    for i in range(length):#左边界渐渐向右逼近
        sums = 0
        for j in A[i:]:
            sums += j
            if sums == m:#背包能够被装满，直接输出背包容量
                return m
            elif m > sums > tot:#在不超过背包容量的前提下，尽可能的装载
                tot = sums
            elif sums > m:#装了这个大件就超过了容量，所以不装
                sums -= j
        if sums < tot:#无法再创新高
            break
    return tot

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

if __name__ == '__main__':
    print('示例1 输出：',load(10,[3,4,8,5]))
    print('示例2 输出：',load(12,[2,3,5,7]))
    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

def package(A,m):
    res=0
    for j in range(2**len(A)):
        tmp = j
        total=0
        count=0
        while tmp!=0:
            total+=A[count]*(tmp%2)
            tmp=tmp//2
            count+=1
        if m>=total >res:
            res=total
    return res

Stubborn

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

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

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

m, A = 10000, [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


(9997, [995, 983, 983, 966, 966, 935, 935, 929, 929, 922, 454])

我运算，就是速度台太行了：(10000,[998, 995, 995, 983, 983, 966, 966, 935, 929, 321, 929])

A = 20000， m = m * 5

(19992, [998, 998, 998, 998, 995, 995, 995, 995, 995, 983, 983, 983, 983, 983, 966, 966, 966, 966, 966, 935, 345])

我运算，就是速度台太行了：(20000,[998, 998, 998, 998, 995, 995, 995, 995, 995, 983, 983, 983, 983, 983, 966, 966, 966, 966, 998, 321, 935])

爱吃鱼的mao

def function(m:int, a:list):
    a.sort(reverse=True)
    res = 0
    for i in range(len(a)):
        add = a[i]
        b = a[i+1:]
        while add <= m:
            for j in range(len(b)):
                if b[j] <= m - add:
                    add += b[j]
                    b = b[j+1:]
                    break
            else:
                break
        #print(add)
        if add > res:
            res = add
    return res

阴阳神万物主

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

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