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

zltzlt

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

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

Unicorn#

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

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

自闭中

华一仙

def f265(m, A):        
    lst = [0] * (m+1)
    for i in range(len(A)):
        for j in range(m, 0, -1):
            if A[i] <= j and lst[j] <= lst[j-A[i]] + A[i]:
                lst[j] = lst[j-A[i]] + A[i]
    return lst[m]

foxiangzun

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

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

def package(weight, weight_most):
        weight.sort()
        lenth = len(weight)
        resultList = [0 for i in range(weight_most + 1)]
        for i in range(lenth) :
                for j in range(weight_most, 0, -1) :
                        if weight[i] <= j :
                                resultList[j] = max(resultList[j], resultList[j - weight[i]] + weight[i])
        return resultList[-1]

Python3005

def bag(m , A):
        value = []
        for n in range(2, len(A)+1):
                p = i.combinations(A, n)
                for each in p:
                        if sum(each) > m:
                                continue
                        else:
                                value.append(sum(each))
        value.sort()
        return value[-1]

Stubborn

def Optimal(m,A):
    length = len(A)
    backing = [[0 * _ for _ in range(m+1)] for _ in range(length+1)]
    max_number = 0

    for j in range(length): # 每件物品 A[i]
        for i in range(m+1):  # 背包的容量:最后
            if i >= A[j]:
                backing[j + 1][i] = backing[j][i - A[j]] + A[j]
                
                if backing[j + 1][i] == m:
                    return m
                if backing[j + 1][i] > max_number:
                    max_number = backing[j + 1][i]
            else:
                  backing[j + 1][i] = max(backing[j][i],backing[j+1][i])

    return max_number

python万

findland

V2.0
穷举，感觉好蠢

def package_1(A):
    
    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
        yield total
def get_max(A,m):
    res=0
    
    for i in (package_1(A)):
        if m>=i>res:
            res=i
    return res
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]

test=get_max(A,m)
print(test)

jerryxjr1220

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

import console; 
console.open();
limit = 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"
A = string.split(A,",");
list = {}
cans = {}
for _,i in A{
        n = tonumber(i);
        table.push(list,n);
        cans[n] = {n}
}

for _,ea in list {
        for ei,ec in cans {
                if ei == ea continue ;
                if table.find(ec,ea) continue ;
                if ea+ei>limit continue ;
                new = table.clone(ec);
                table.push(new,ea);
                cans[ea+ei] = new;
        }
}

s = ""
for k,v in cans{
        //console.log(k);
        //console.log(table.unpack(v));
        s ++= tostring(k) ++ '\r\n';
        for _,i in v {
                s ++= tostring(i) ++ '\t';
        }
        s ++= '\r\n';
}

console.log(s)

string.save("temp.txt", s)

console.pause(true);

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

jdzzj

 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[j]
            if size>m:
                size-=B[j]
                continue
            
        sizes.append(size)
            
    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
还是会超时……

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