首页 > 试题广场 >

牛牛的背包问题

[编程题]牛牛的背包问题
  • 热度指数：47375 时间限制：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种情况。
算法知识视频讲解
添加回答
JavaScript
萌萌萌哒头像 萌萌萌哒
JavaScript(Node) 😎题目:网易-背包问题 
//递归
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
let inArr = []
rl.on('line', line => {
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 2) {
        let n = +inArr[0].split(' ')[0]//零食的数量
        let w = +inArr[0].split(' ')[1]//背包的容量
        let snackArr = inArr[1].split(' ').map(item => +item)
        let snackSum = snackArr.reduce((acc, cur) => acc+cur,0)
        if(snackSum <= w) {
            console.log(2**n)//Math.pow(2,n)
        }else {
            console.log(f(n - 1,w))
        }
        function f (i, restW) {
            if(restW <= 0) {
                return 0
            }
            if(i === 0) {
                if(snackArr[i] > restW) {
                    return 1
                }
                else {
                    return 2
                }
            }
            return f(i-1, restW - snackArr[i]) + f(i-1, restW)
        }
         
    }
})
编辑于 2020-02-26 10:26:44 回复(0)
JavaScript
AC手环头像 AC手环 
let [n, w] = readline().split(' ').map(d=>+d)
let snacks = readline().split(' ').map(d=>+d)
let result = 0
let sum = snacks.reduce((p,d)=>p+d,0)


if(sum <= w){
    console.log(Math.pow(2, n))
}else{
    snacks.sort()
    dfs(0, 0)
    console.log(result)
}


function dfs(total, i){
    if(i >= n){
        result++
        return
    }
    if(total+snacks[i] > w){  // 拿不起
        dfs(total, i+1)  // 不拿这包零食
    }else{  // 拿得起
        dfs(total, i+1)  // 不拿这包零食
        dfs(total+snacks[i], i+1)  // 拿这包零食
    }
}
编辑于 2019-08-20 14:31:55 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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