牛牛的背包问题

[编程题]牛牛的背包问题

热度指数：193 时间限制：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

输出

说明

三种零食总体积小于10,于是每种零食有放入和不放入两种情况，一共有2*2*2 = 8种情况。

算法知识视频讲解

为什么不问问神奇海螺呢

用人用sort暴力dfs都过了= =，拜托能不能数据出用心点。折半算法+upper_bound

发表于 2018-12-06 20:30:55 回复(0)

Python 3

牛客557410249号

n,w = list(map(int,input().split()))
lst = list(map(int,input().split()))
import itertools
result=[]
i=0
while i < len(lst):
    if lst[i]>w:
        lst.pop(i)
        i+=1
    else:
        i+=1
for j in range(0,len(lst)+1):
    result.extend(list(itertools.combinations(lst, j)))
for i in range(len(result)):
    if sum(result[i])>w:
        result.pop(i)

print(len(result))
#超过内存了，不会了

发表于 2022-06-10 21:27:38 回复(0)