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

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

复制代码

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

跳转到最佳答案楼层

zhuangzhuangmvp

1

赵容博

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

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

Vmtayvj

背包问题 动态规划QQ

塔利班

1. def f329(s,v,c):
   
2.     def dp(a,lv,lc):
   
3.         l=[]
   
4.         for i,e in enumerate(lc):
   
5.             if e<=a:
   
6.                 vv=lv.pop(i)
   
7.                 cc=lc.pop(i)
   
8.                 l.append(dp(a-e,lv,lc)+vv)
   
9.                 lv.insert(i,vv)
   
10.                 lc.insert(i,cc)
    
11.         return max(l+[0])
    
12.     return dp(s,v,c)

复制代码

776667

1. from itertools import combinations
   
2. 
   
3. def fun329(s,v,c):
   
4.     max_c = 0
   
5.     result_list = []
   
6.     value_list = []
   
7.     for i in range(len(c)):
   
8.         if max_c == 0:
   
9.             max_c = i+1
   
10.         elif sum(sorted(c)[:i+1]) <= s:
    
11.             max_c = i+1
    
12.         else:
    
13.             break
    
14.     count = [i for i in range(len(v))]
    
15.     for i in range(1,max_c+1):
    
16.         for j in combinations(count,i):
    
17.             if j not in result_list and sum([c[n] for n in j])<=s:
    
18.                 result_list.append(j)
    
19.     for i in result_list:
    
20.         value_list.append(sum([v[j] for j in i]))
    
21.     return max(value_list)

复制代码

TJBEST

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

546623863

1. def fun329(s,v,c):
   
2.     if(s == 0):
   
3.         return 0
   
4.     if(sum(c) <= s):
   
5.         return sum(v)
   
6.     v.insert(0,0)
   
7.     c.insert(0,0)
   
8.     length = len(c)
   
9.     value = [[0 for i in range(s+1)] for i in range(length)]
   
10.     for i in range(1,length):
    
11.         for j in range(1,s+1):
    
12.             if c[i] <= j:
    
13.                 value[i][j] = max(value[i-1][j-c[i]]+v[i],value[i-1][j])
    
14.             else:
    
15.                 value[i][j] = value[i-1][j]
    
16.     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

1. def f329(s,v,c):
   
2.     m=0
   
3.     for i in range(len(v)):
   
4.         if v[i]>s:continue
   
5.         elif v[i]>m:
   
6.             m=v[i]
   
7.             
   
8.         a=[i]
   
9.         value=v[i]
   
10.         volume=c[i]
    
11.       
    
12.         if i==len(v)-1:
    
13.             break
    
14.         
    
15.         x=i+1
    
16.         while len(a):            
    
17.             if volume+c[x]>s:
    
18.                 x+=1
    
19.             else:
    
20.                 a.append(x)
    
21.                 value+=v[x]
    
22.                 volume+=c[x]
    
23.                 if value>m:m=value
    
24.                 x+=1
    
25.                 #print(a,value,volume)
    
26.             while x==len(v):
    
27.                 x=a.pop(len(a)-1)
    
28.                 value-=v[x]
    
29.                 volume-=c[x]
    
30.                 x+=1
    
31.     return m
    

复制代码

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

fan1993423

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

复制代码

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

TJBEST

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

1. def fun329(s,v,c):
   
2. 
   
3.     def findLowEqual(index,res):
   
4.         if index + 1 >= M or c_list[M-1]>res:
   
5.             return -1
   
6.         else:
   
7.             bottom = index + 1
   
8.             top = M
   
9.             while True:
   
10.                 middle = (bottom + top)//2
    
11.                 temp = c_list[middle]
    
12.                 if temp > res:
    
13.                     bottom = middle
    
14.                 else:
    
15.                     if middle == index + 1 or c_list[middle - 1]>res:
    
16.                         return middle
    
17.                     else:
    
18.                         top = middle
    
19.                         
    
20.     def inner(index,res):
    
21.         start = findLowEqual(index,res)
    
22.         if  start < 0:
    
23.             maxNum[0] = max(maxNum[0],tempTotal[0])
    
24.         else:
    
25.             for index in range(start,M):
    
26.                 div = s // c_list[start]
    
27.             for i in range(0,min(div+1,number_list[start]+1)):
    
28.                 tempTotal[0] += sum(dictionary[c_list[start]][0:i])
    
29.                 inner(start,res - i*c_list[start])
    
30.                 tempTotal[0] -= sum(dictionary[c_list[start]][0:i])
    
31.         
    
32.     lenth = len(c)
    
33.    
    
34.     if lenth == 0:
    
35.         return 0
    
36.    
    
37.     dictionary = {}#c:[v]
    
38.     for index in range(0,lenth):
    
39.         tempC = c[index]
    
40.         tempV = v[index]
    
41.         try:
    
42.             dictionary[tempC].append(tempV)
    
43.         except Exception:
    
44.             tempList = [tempV]
    
45.             dictionary[tempC] = tempList
    
46.    
    
47.     number_list = []
    
48.     for eachC in dictionary:
    
49.         number_list.append(len(dictionary[eachC]))
    
50.         dictionary[eachC].sort()
    
51.         dictionary[eachC].reverse()
    
52.         
    
53.     c_list = list(dictionary.keys())
    
54.     c_list.sort()
    
55.     c_list.reverse()
    
56.     M = len(c_list)
    
57.    
    
58.     maxNum = [0]
    
59.     tempTotal = [0]
    
60.     for index in range(0,M):
    
61.         div = s // c_list[index]
    
62.         for i in range(0,min(div+1,number_list[index]+1)):
    
63.             tempTotal[0] += sum(dictionary[c_list[index]][0:i])
    
64.             inner(index,s - i*c_list[index])
    
65.             tempTotal[0] -= sum(dictionary[c_list[index]][0:i])
    
66.     return maxNum[0]

复制代码

fan1993423

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

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

kinkon

1. def f329(s,v,c):
   
2.     n=[0]
   
3.     for i,j in enumerate(c):
   
4.         if j<=s:
   
5.             nv,nc=v.pop(i),c.pop(i)
   
6.             n.insert(0,f329(s-j,v,c)+nv)
   
7.             v.insert(i,nv)
   
8.             c.insert(i,nc)
   
9.     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

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

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

复制代码

zltzlt

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

输入大数据超时