首页 > 试题广场 >

牛牛的背包问题

[编程题]牛牛的背包问题
  • 热度指数：47663 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。

输入描述:
输入包括两行
第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。
第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积。


输出描述:
输出一个正整数, 表示牛牛一共有多少种零食放法。
示例1

输入

3 10
1 2 4

输出

8

说明

三种零食总体积小于10,于是每种零食有放入和不放入两种情况，一共有2*2*2 = 8种情况。
算法知识视频讲解
添加回答
Python
咖啡配牛奶头像 咖啡配牛奶
AC100 
N,W = list(map(int,input().split()))
V = list(map(int, input().split()))
 
def dfs(V,idx,weight):
    if idx == len(V):
        return 1
    
    if weight-V[idx]>0:
        return dfs(V,idx+1,weight-V[idx])+dfs(V,idx+1,weight)
    else:
        return dfs(V,idx+1,weight)
if sum(V)<W:
    print(2**N)
else:
    print(dfs(V,0,W))

发表于 2020-08-31 19:53:50 回复(0)
Python
sky游荡头像 sky游荡
很尴尬，加了个感觉不影响复杂度的东西。算是针对测试用例特别操作的。
思路:求子集，判断是否超重，没超重加一。 
n,w = list(map(int,input().split()))
weight = list(map(int,input().split()))
c = 0
class A:
    def __init__(self):
        self.c = 0
    def get_all(self,w,weight,tmp):
        if not weight&nbs***bsp;sum(tmp)>w:
            return 
        else:        
            tmp.append(weight[0])
            if sum(tmp)<=w:
                self.c+=1
            self.get_all(w,weight[1:],tmp)
            tmp.pop()
            self.get_all(w,weight[1:],tmp)
        return self.c
if sum(weight)<=w:
        print(2**n)
else:
    print(A().get_all(w,weight,[])+1)


发表于 2020-04-13 00:03:26 回复(0)
Python
Narudo头像 Narudo
采用递归的方式进行解析：
1.首先过滤掉列表中大于w的元素，然后对其从从小到大进行排序
2.然后，对列表中的所有元素的和与w比较，如果小于w，则证明列表中的元素无论怎么组合都满足背包容量要求，所以共有2的n次方中方法：v
3：如果大于w，采用深度优先的算发，对列表进行遍历。每次遍历得到和与w进行比较，小于等于w则证明符合要求，再次进行下一层递归（start，len（v）），否则返回上层。 

import sys
from copy import deepcopy
def countWays(v,w,start,init_value,count):
    length = len(v)
    if length <= start:
        return count
    for i in range(start,length):
        init_value += v[i]
        if init_value <= w:
            count += 1
            count = countWays(v,w,i+1,init_value,count)
            init_value -= v[i]
        else:
            return count
    return count
    
if __name__ == "__main__":
    line = sys.stdin.readline()
    n,w = map(int,line.strip().split())
    line = sys.stdin.readline()
    v = list(map(int,line.strip().split()))
    count = 0
    v = [i for i in v if i <= w]
    v.sort()
    if sum(v)<=w:
        count = 2**len(v)
    else:
        if len(v) != 0:
            count = len(v)
            level = 1
            init_value = 0
            for start in range(len(v)):
                init_value = v[start]
                count = countWays(v,w,start+1,init_value,count)
            count += 1
    print(count)


发表于 2020-01-13 11:50:15 回复(0)
Python
国企程序锅头像 国企程序锅 
# Python Solution
# JingLiu
# 背包问题，对于第一件物品分两种情况，取和不取。
while True:
    try:
        n, w = list(map(int, input().strip().split(' ')))
        v = list(map(int, input().strip().split(' ')))
            v = sorted(v)
        def count(w, v):
            if w <= v[0]:
                return 1
            if sum(v) <= w:
                return 2 ** len(v)
            if v[0] <= w:
                return count(w - v[0], v[1:]) + count(w, v[1:])
        print(count(w, v))
    except:
        break

编辑于 2019-08-28 18:38:05 回复(0)
Python
share1722头像 share1722

看到很多前排答案都是用的递归来避免空间复杂度 但是这样时间复杂度就很高了啦 图片说明 下面贴出在递归过程中加入Cache方式 能将算法复杂度降到图片说明 空间复杂度也不会炸掉 代码如下

import sys

def solver(w, v, pos, dp):
    if (w, pos) in dp:
        return dp[(w, pos)]
    if w < 0:
        return 0
    if pos == len(v):
        return 1 if w >= 0 else 0
    else:
        if (w, pos + 1) not in dp:
            dp[(w, pos + 1)] = solver(w, v, pos + 1, dp)
        if (w - v[pos]) not in dp:
            dp[(w - v[pos], pos + 1)] = solver(w - v[pos], v, pos + 1, dp)
        dp[(w, pos)] = dp[(w, pos + 1)] + dp[(w - v[pos], pos + 1)]
        return dp[(w, pos)]

if __name__ == '__main__':

    line = list(map(int, sys.stdin.readline().strip().split()))
    n, w = line[0], line[1]
    v = list(map(int, sys.stdin.readline().strip().split()))
    if sum(v) <= w:
        print(2**n)
        exit(0)
    print(solver(w, v, 0, dict()))
发表于 2019-06-09 10:09:39 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 穷举 网易 高级算法 2019 Java工程师
来自：网易2019实习生招聘...
上传者：小小
难度：
5条回答 31558浏览

热门推荐

通过挑战的用户

查看代码

相关试题

牛牛的背包问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号