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

zltzlt

今天的题目：

给出一个非负整数 s 代表背包容量。给出 len(c) 件物品，第 a 件物品的价值为 v[a]，体积为 c[a]。

求这个背包最多能装多少价值的物品，返回总价值。

说明：len(c) == len(v)。

注意：每件物品只能用一次。

示例 1：

输入：s = 10, v = [1,2,3], c = [3,5,7]
输出：4
解释：将第 0 件和第 2 件物品放进背包。

示例 2：

输入：s = 10, v = [1,5,3], c = [4,5,7]
输出：6
解释：将第 0 件和第 1 件物品放进背包。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

fan1993423

2020-2-11 23:26:31

def fun329(s,v,c):
    list_rel=sorted(list(zip(v,c)),key=lambda x:x[0],reverse=True)
    copy_s,count,result,length=s,0,0,len(list_rel)
    for i in range(length):
        for j in range(i,length):
            s-=list_rel[j][1]
            if s>=0:
                count+=list_rel[j][0]
            else:
                s+=list_rel[j][1]
        result=max(count,result)
        count,s=0,copy_s
    return result if result>0 else '背包太小，装不下任何东西'

我不知道要不要考虑背包装不下任何东西的情况，为了保守起见，还是多加个判别式

跳转到最佳答案楼层

zhuangzhuangmvp

1

赵容博

zhuangzhuangmvp 发表于 2020-2-11 19:31
1

刚才我看到有人回了，还以为答出来了
结果...

Vmtayvj

背包问题 动态规划QQ

塔利班

def f329(s,v,c):
    def dp(a,lv,lc):
        l=[]
        for i,e in enumerate(lc):
            if e<=a:
                vv=lv.pop(i)
                cc=lc.pop(i)
                l.append(dp(a-e,lv,lc)+vv)
                lv.insert(i,vv)
                lc.insert(i,cc)
        return max(l+[0])
    return dp(s,v,c)

776667

from itertools import combinations

def fun329(s,v,c):
    max_c = 0
    result_list = []
    value_list = []
    for i in range(len(c)):
        if max_c == 0:
            max_c = i+1
        elif sum(sorted(c)[:i+1]) <= s:
            max_c = i+1 
        else:
            break
    count = [i for i in range(len(v))]
    for i in range(1,max_c+1):
        for j in combinations(count,i):
            if j not in result_list and sum([c[n] for n in j])<=s:
                result_list.append(j)
    for i in result_list:
        value_list.append(sum([v[j] for j in i]))
    return max(value_list)

TJBEST

体积和价值都是 正整数吗？而且有可能重复？

546623863

def fun329(s,v,c):
    if(s == 0):
        return 0
    if(sum(c) <= s):
        return sum(v)
    v.insert(0,0)
    c.insert(0,0)
    length = len(c)
    value = [[0 for i in range(s+1)] for i in range(length)]
    for i in range(1,length):
        for j in range(1,s+1):
            if c[i] <= j:
                value[i][j] = max(value[i-1][j-c[i]]+v[i],value[i-1][j])
            else:
                value[i][j] = value[i-1][j]
    return value[-1][-1]

动态规划吧

坑得飞起

def func(s,v,c):
    danjia, ans =[], 0
    for i in range(len(c)):
        danjia += [[v[i]/c[i],i]]
    danjia.sort(reverse=True)
    for i in danjia :
        if s >= c[i[1]] :
            ans += v[i[1]]
            s = s - c[i[1]]
        if s == 0 :
            break   
    return ans

William4869

def f329(s,v,c):
    m=0
    for i in range(len(v)):
        if v[i]>s:continue
        elif v[i]>m:
            m=v[i]
            
        a=[i]
        value=v[i]
        volume=c[i]
       
        if i==len(v)-1:
            break
        
        x=i+1
        while len(a):            
            if volume+c[x]>s:
                x+=1
            else:
                a.append(x)
                value+=v[x]
                volume+=c[x]
                if value>m:m=value
                x+=1
                #print(a,value,volume)
            while x==len(v):
                x=a.pop(len(a)-1)
                value-=v[x]
                volume-=c[x]
                x+=1
    return m

无脑深搜遍历玩法，感觉会超时，，回头我去看看动态规划是个什么东西

fan1993423

def fun329(s,v,c):
    list_rel=sorted(list(zip(v,c)),key=lambda x:x[0],reverse=True)
    copy_s,count,result,length=s,0,0,len(list_rel)
    for i in range(length):
        for j in range(i,length):
            s-=list_rel[j][1]
            if s>=0:
                count+=list_rel[j][0]
            else:
                s+=list_rel[j][1]
        result=max(count,result)
        count,s=0,copy_s
    return result if result>0 else '背包太小，装不下任何东西'

我不知道要不要考虑背包装不下任何东西的情况，为了保守起见，还是多加个判别式

TJBEST

先来个简单的 背包问题的分治算法 我忘了 先用这个试试 分治算法我再看看
#给出一个非负整数 s 代表背包容量。给出 len(c) 件物品，第 a 件物品的价值为 v[a]，体积为 c[a]。
#求这个背包最多能装多少价值的物品，返回总价值。

def fun329(s,v,c):

    def findLowEqual(index,res):
        if index + 1 >= M or c_list[M-1]>res:
            return -1
        else:
            bottom = index + 1
            top = M
            while True:
                middle = (bottom + top)//2
                temp = c_list[middle]
                if temp > res:
                    bottom = middle
                else:
                    if middle == index + 1 or c_list[middle - 1]>res:
                        return middle
                    else:
                        top = middle
                        
    def inner(index,res):
        start = findLowEqual(index,res)
        if  start < 0:
            maxNum[0] = max(maxNum[0],tempTotal[0])
        else:
            for index in range(start,M):
                div = s // c_list[start]
            for i in range(0,min(div+1,number_list[start]+1)):
                tempTotal[0] += sum(dictionary[c_list[start]][0:i])
                inner(start,res - i*c_list[start])
                tempTotal[0] -= sum(dictionary[c_list[start]][0:i])
        
    lenth = len(c)
   
    if lenth == 0:
        return 0
    
    dictionary = {}#c:[v]
    for index in range(0,lenth):
        tempC = c[index]
        tempV = v[index]
        try:
            dictionary[tempC].append(tempV)
        except Exception:
            tempList = [tempV]
            dictionary[tempC] = tempList
    
    number_list = []
    for eachC in dictionary:
        number_list.append(len(dictionary[eachC]))
        dictionary[eachC].sort()
        dictionary[eachC].reverse()
        
    c_list = list(dictionary.keys())
    c_list.sort()
    c_list.reverse()
    M = len(c_list)
    
    maxNum = [0]
    tempTotal = [0]
    for index in range(0,M):
        div = s // c_list[index]
        for i in range(0,min(div+1,number_list[index]+1)):
            tempTotal[0] += sum(dictionary[c_list[index]][0:i])
            inner(index,s - i*c_list[index])
            tempTotal[0] -= sum(dictionary[c_list[index]][0:i])
    return maxNum[0]

fan1993423

TJBEST 发表于 2020-2-11 23:31
先来个简单的 背包问题的分治算法 我忘了 先用这个试试 分治算法我再看看
#给出一个非负整数 s  ...

66行代码啊，牛，那么多代码我肯定脑壳中间要多动一下

kinkon

def f329(s,v,c):
    n=[0]
    for i,j in enumerate(c):
        if j<=s:
            nv,nc=v.pop(i),c.pop(i)
            n.insert(0,f329(s-j,v,c)+nv)
            v.insert(i,nv)
            c.insert(i,nc)
    return max(n)

ouyunfu

s = 10
v = [1,2,3,4]
c = [3,5,7,3]
L=[]
def f329(s:int,v:list,c:list)->int:
    if sum(c)<s:
        L.append(sum(v))
        return L
    else:
        for i in range(len(c)):
            c1=c.copy()
            v1=v.copy()
            c1.remove(c1[i])
            v1.remove(v1[i])
            if sum(c1)<=s:
                L.append(sum(v1))
            else:
                f329(s,v1,c1)
    return max(L)

print(f329(s,v,c))

TJBEST

fan1993423 发表于 2020-2-11 23:36
66行代码啊，牛，那么多代码我肯定脑壳中间要多动一下

还行吧，代码长的好处在于不用动脑子 就是速度慢点

TJBEST

请不要封题，下午我便可给出 无递归的的解法

office

读了半天，没怎么读懂题目

TJBEST

第二个版本，背包求解，没用递归，挺快的

def fun329(s,v,c):
    #0/1背包问题 由于 给的条件没有说 每个同体积同价值的个数（或无限） 只能按照0/1背包去算
    #采用循环遍历 
    #s是容量 v是价值 c是体积
    M = len(v)
    f = [0 for i in range(0,s + 1)]#临时变量 s + 1长度
    for i in range(0,M):
        for m in range(s,0,-1):
            res = m - c[i]
            if res >= 0:
                f[m] = max(f[m],f[res] + v[i])
            else:
                break
    return f.pop()

zltzlt

塔利班 发表于 2020-2-11 20:31

输入大数据超时