论坛 › Python交流 › Python：每日一题 329

zltzlt 发表于 2020-2-11 18:55:08

Python：每日一题 329

本帖最后由 zltzlt 于 2020-2-11 18:58 编辑

今天的题目：

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

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

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

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

示例 1：

输入：s = 10, v = , c =
输出：4
解释：将第 0 件和第 2 件物品放进背包。
示例 2：

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

{:10_298:}欢迎大家一起答题！{:10_298:}

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

1

赵容博 发表于 2020-2-11 19:32:43

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

刚才我看到有人回了，还以为答出来了
结果...
{:10_313:}{:10_293:}

Vmtayvj 发表于 2020-2-11 19:54:53

背包问题 动态规划QQ

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

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+)
    return dp(s,v,c)

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

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 =
    for i in range(1,max_c+1):
      for j in combinations(count,i):
            if j not in result_list and sum( for n in j])<=s:
                result_list.append(j)
    for i in result_list:
      value_list.append(sum( for j in i]))
    return max(value_list)

TJBEST 发表于 2020-2-11 21:31:52

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

546623863 发表于 2020-2-11 21:40:51

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 = [ for i in range(length)]
    for i in range(1,length):
      for j in range(1,s+1):
            if c <= j:
                value = max(value]+v,value)
            else:
                value = value
    return value[-1][-1]

动态规划吧

坑得飞起 发表于 2020-2-11 22:01:02

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

William4869 发表于 2020-2-11 22:10:27

本帖最后由 William4869 于 2020-2-11 22:15 编辑

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


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

fan1993423 发表于 2020-2-11 23:26:31

本帖最后由 fan1993423 于 2020-2-11 23:34 编辑

def fun329(s,v,c):
    list_rel=sorted(list(zip(v,c)),key=lambda x:x,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
            if s>=0:
                count+=list_rel
            else:
                s+=list_rel
      result=max(count,result)
      count,s=0,copy_s
    return result if result>0 else '背包太小，装不下任何东西'
我不知道要不要考虑背包装不下任何东西的情况，为了保守起见，还是多加个判别式

TJBEST 发表于 2020-2-11 23:31:39

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

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

fan1993423 发表于 2020-2-11 23:36:28

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

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

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

本帖最后由 kinkon 于 2020-2-12 00:00 编辑

def f329(s,v,c):
    n=
    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 发表于 2020-2-12 01:07:18

s = 10
v =
c =
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)
            v1.remove(v1)
            if sum(c1)<=s:
                L.append(sum(v1))
            else:
                f329(s,v1,c1)
    return max(L)

print(f329(s,v,c))

TJBEST 发表于 2020-2-12 10:37:05

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

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

TJBEST 发表于 2020-2-12 11:08:39

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

office 发表于 2020-2-12 11:26:29

读了半天，没怎么读懂题目{:10_277:}

TJBEST 发表于 2020-2-12 11:57:35

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

zltzlt 发表于 2020-2-12 13:52:50

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


输入大数据超时

查看完整版本: Python：每日一题 329