首页 > 试题广场 >

牛牛的背包问题

[编程题]牛牛的背包问题
  • 热度指数：673 时间限制：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种情况。
算法知识视频讲解
添加回答
pein531头像 pein531

记忆化搜索

感觉有点问题，但是AC了，当零食总体积不超过背包体积时怎么背都可以，每个零食都可以有两种选择：选与不选。一共种方案。否则就是个背包问题，从左往右进行尝试，用记忆化搜索缓存中间结果。 
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), w = Integer.parseInt(params[1]);
        params = br.readLine().split(" ");
        int[] v = new int[n];
        long sum = 0;
        for(int i = 0; i < n; i++){
            v[i] = Integer.parseInt(params[i]);
            sum += v[i];
        }
        if(sum <= w){
            System.out.println((int)Math.pow(2, n));
        }else{
            Map<Integer, Integer> dp = new HashMap<>();
            dp.put(0, 1);
            System.out.println(dfs(v, w, 0, dp));
        }
    }
    
    private static int dfs(int[] v, int rest, int index, Map<Integer, Integer> dp) {
        if(rest < 0){
            return 0;
        }
        if(index == v.length){
            if(!dp.containsKey(rest)){
                dp.put(rest, 1);
            }
        }else{
            if(!dp.containsKey(rest)){
                int cnt = dfs(v, rest, index + 1, dp) + dfs(v, rest - v[index], index + 1, dp);
                dp.put(rest, cnt);
            }
        }
        return dp.get(rest);
    }
}

暴力递归

这个应该没有问题，但是复杂度比较高 
import java.io.*;
import java.util.*;

public class Main {
    private static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), w = Integer.parseInt(params[1]);
        params = br.readLine().split(" ");
        int[] v = new int[n];
        long sum = 0;
        for(int i = 0; i < n; i++){
            v[i] = Integer.parseInt(params[i]);
            sum += v[i];
        }
        if(sum <= w){
            System.out.println((int)Math.pow(2, n));
        }else{
            dfs(v, w, 0);
            System.out.println(count);
        }
    }
    
    private static void dfs(int[] v, int rest, int index) {
        if(rest < 0){
            return;      // 背包容量不够了，本次尝试无效
        }
        if(index == v.length){
            count++;     // 到头了，生成一种方案
        }else{
            dfs(v, rest, index + 1);      // 不选index编号的零食
            dfs(v, rest - v[index], index + 1);     // 选index编号的零食
        }
    }
}

发表于 2022-03-18 11:45:21 回复(0)
dut_zxy头像 dut_zxy 
#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:     Solution(int n, int w, vector<long long> &v) :_n(n), _w(w), _ans(1)     {         _v.swap(v);     }     int func()     {         for (int i = 0; i < _v.size(); i++)         {             help(_v[i], i + 1);         }         return _ans;     }
private:     int _n;     int _w;     int _ans;     vector<long long> _v;
private:     void help(long long cw, int index)     {         if (cw > _w)         {             return;         }         if (cw <= _w)         {             _ans++;         }         for (int i = index; i < _v.size(); i++)         {             cw += _v[i];             help(cw, i + 1);             cw -= _v[i];         }     }
};

int main()
{     int n, w;     cin >> n >> w;     vector<long long> v(n);     for (int i = 0; i < n; i++)     {         cin >> v[i];     }     Solution s(n, w, v);     cout << s.func() << endl;     return 0;
}

发表于 2018-08-07 16:29:13 回复(0)
蛟龙吐火球丰头像 蛟龙吐火球丰 
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int cnt,n;
LL w;

void walk(vector<LL>& co,int idx,LL curw)
{
    if(curw>w)return;
    if(idx>=n){cnt++;return;}
    walk(co,idx+1,curw+co[idx]);
    walk(co,idx+1,curw);   
}
int main()
{
    while(cin>>n>>w)
    {
        vector<LL> co(n);
        LL sum=0;
        for(int i=0;i<n;i++)
        {
            cin>>co[i];
            sum+=co[i];
        }
        if(sum<=w){cout<<(1<<n)<<endl;continue;}
        cnt=0;
        walk(co,0,0);
        cout<<cnt<<endl;          
    }
}
编辑于 2018-08-10 09:12:30 回复(0)
chestnut7头像 chestnut7

PYTHON,递归

line = raw_input()
n = int(line.split(' ')[0])
w = int(line.split(' ')[1])
line = raw_input()
v = []
for i in range(n):
    v.append(int(line.strip().split(' ')[i]))
ans = 0
def main(v, w): 
    global ans 
    if sum(v) <= w:
        print 2**(len(v))
    else:
        v.sort()
        dfs(0, 0) 
        print ans 

def dfs(su, loc):
    global ans 
    if su > w:
        return 
    if su <= w:
        ans += 1
    for i in range(loc, n):
        dfs(su+v[i], i+1)
main(v, w)
发表于 2018-06-26 22:54:07 回复(0)
提交观点

问题信息

穷举 网易 算法工程师 高级算法 2018
上传者：小小
难度：
4条回答 3195浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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