[已解决]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 '背包太小，装不下任何东西'

复制代码

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

跳转到最佳答案楼层

zltzlt

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

输入大数据超时

zltzlt

776667 发表于 2020-2-11 21:16

超时

zltzlt

546623863 发表于 2020-2-11 21:40
动态规划吧

输入大数据超出内存限制

zltzlt

坑得飞起 发表于 2020-2-11 22:01
def func(s,v,c):
    danjia, ans =[], 0
    for i in range(len(c)):

解答错误

输入：

1. s = 195387950,
   
2. v = [277996895,67034365,215265173,17927245,196665561,122553408,229181848,37953684,130611629,18096518,221937650,16569090,215131206,246680015,75894559,177999561,249070738,321264238,110845985,176753214],
   
3. s = [228482420,301972492,81534843,235620330,102486915,234004708,18881095,194477148,60832041,118314582,292428017,74861428,43938149,86992501,239732394,193891049,112838218,127944264,276821750,172241156]

复制代码

输出：690993069
预期结果：765577292

zltzlt

William4869 发表于 2020-2-11 22:10
无脑深搜遍历玩法，感觉会超时，，回头我去看看动态规划是个什么东西

超时

zltzlt

fan1993423 发表于 2020-2-11 23:26
我不知道要不要考虑背包装不下任何东西的情况，为了保守起见，还是多加个判别式

60 ms

zltzlt

kinkon 发表于 2020-2-11 23:59

会超时

zltzlt

ouyunfu 发表于 2020-2-12 01:07
s = 10
v = [1,2,3,4]
c = [3,5,7,3]

https://fishc.com.cn/forum.php?m ... peid%26typeid%3D441

zltzlt

ouyunfu 发表于 2020-2-12 01:07
s = 10
v = [1,2,3,4]
c = [3,5,7,3]

会超时

zltzlt

TJBEST 发表于 2020-2-12 11:57
第二个版本，背包求解，没用递归，挺快的

超出内存限制

zltzlt

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

超时

zltzlt

fan1993423 发表于 2020-2-12 15:07
是不是只有我一个没有超时啊

是

zltzlt

TJBEST 发表于 2020-2-12 15:27
超出内存？我的空间 是o(n)的 n是个数 不应该吧

因为 n 很大

zltzlt

TJBEST 发表于 2020-2-12 17:19
您在试试这个，我尝试缩小了点空间

会超时