首页 > 试题广场 >

牛牛的背包问题

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

热度指数：47323 时间限制：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种情况。

算法知识视频讲解

C/C++

数学&curren;lover

这一类背包问题有两种方法，一种是当物品个数n较少，但是背包大小m比较大时采用指数级的枚举搜索，复杂度为O(2^n)

另一种是当背包比较小的时候采用动态规划O(nm)

这道题明显是属于第一种。但是2^30的复杂度是不可以接受的，因此我们可以采用中途相遇法。把我们能接受的前15个物品先进行第一次枚举搜索，然后再对剩下的物品进行第二次枚举搜索。把第二次枚举搜索出来的结果(至多2^15=32768个答案)存入数组并排序，枚举第一次搜出来的结果，计算出还剩下多少背包体积还能装，在第二次的结果中进行二分搜索，并把两次搜索的结果进行相乘(乘法原理)。再把所有的结果进行相加(加法原理)，就是答案了。

我为了让小数据算的快一些，当n<20时直接枚举搜索出答案了。

当然也可以把物品分成n/2和n-n/2两部分。

总复杂度是O(2^(n/2)*n)

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
long long a[50];
int main()
{
    int n;
    long long m;
    cin>>n>>m;
    for(int i=0;i<n;++i)
        cin>>a[i];
    if(n<20)
    {
        int ans=0;
        for(int i=0;i<1<<n;++i)
        {
            long long weight=0;
            for(int j=0;j<n;++j)
                if((i&(1<<j))!=0)
                    weight+=a[j];
            if(weight<=m)
                ans++;
        }
        cout<<ans<<endl;
        return 0;
    }
    long long b[20];
    for(int i=0;i<15;++i)
        b[i]=a[i];
    long long c[20];
    for(int i=0;i<n-15;++i)
        c[i]=a[i+15];
    map<long long,int>mp;
    for(int i=0;i<(1<<15);++i)
    {
        long long weight=0;
        for(int j=0;j<15;++j)
            if((i&(1<<j))!=0)
                weight+=b[j];
        if(weight>m)
            continue;
        if(mp.find(weight)!=mp.end())
            mp[weight]++;
        else mp[weight]=1;
    }
    //cout<<mp.size()<<endl;
    int last=n-15;
    map<long long,int>another;
    for(int i=0;i<(1<<last);++i)
    {
        long long weight=0;
        for(int j=0;j<last;++j)
            if((i&(1<<j))!=0)
                weight+=c[j];
        if(weight>m)
            continue;
        if(another.find(weight)!=another.end())
            another[weight]++;
        else another[weight]=1;
    }
    vector<pair<long long,int> >vec;
    for(map<long long,int>::iterator it=another.begin();it!=another.end();++it)
        vec.push_back(make_pair(it->first,it->second));
    for(int i=1;i<vec.size();++i)
       vec[i].second+=vec[i-1].second;
    long long ans=0;
    for(map<long long,int>::iterator it=mp.begin();it!=mp.end();++it)
    {
        long long p=m-(it->first);
        int q=lower_bound(vec.begin(),vec.end(),make_pair(p,0))-vec.begin();
        ans+=vec[q-1].second*(it->second);
    }
    cout<<ans<<endl;
}

发表于 2018-03-28 01:40:48 回复(4)

lewis_c++

/*前几个答案的递归是有问题的，在调用的时候不需要for循环对每个i调用
递归本身就包含了这种循环*/
#include<bits/stdc++.h>
using namespace std;
long ans=0;
int n;
long w;
vector<long>value;
void dfs(long sum,int loc);
int main()
{
    cin>>n>>w;
    long total=0;
    for(int i=0;i<n;++i){
        int b;
        cin>>b;
        value.push_back(b);
        total+=value[i];
    }
    if(total<=w)
        ans=pow(2,n);
    else{
        sort(value.begin(),value.end());
        dfs(0,0);
    }
    cout<<ans<<endl;
    return 0;
}
void dfs(long sum,int loc)
{
    if(sum>w)
        return ;
    if(sum<=w){
        ++ans;
    }
    for(int i=loc;i<n;++i){
        dfs(sum+value[i],i+1);
    }
}

编辑于 2018-05-14 08:23:15 回复(12)

Polestar_a

N,W = list(map(int,input().split()))
V = list(map(int, input().split()))

def count(W, V):
    if W<=0:return 1
    if len(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:])
    else:
        return count(W, V[1:])
print(count(W,V))

发表于 2019-07-05 16:33:22 回复(12)

marioZYN

这道题采用最基本的递归做法的话，每一个物品都要考虑放入或者不放入两个情况，算法复杂度为O（2^n）。代码如下：函数参数值有两个

remain_items:剩下需要考虑的物品
available_weight: 当前可用的容量

def brute_force(remain_items, available_weight):
    if len(remain_items) == 0:
        return 1
    elif available_weight == 0:
        return 1
    else:
        item = remain_items[0]
        if item < available_weight:
            return brute_force(remain_items[1:], available_weight-item) + brute_force(remain_items[1:], available_weight)
        else:
            return brute_force(remain_items[1:], available_weight)

这个基本的recursion AC为80%。我们可以做一下简单的调整。比如，

如果当前的物品的重量和小于可用容量，就直接输出 2^n
可以把v数组从小到大排序，这样当当前的item 重量 > available_weight时就不用继续递归下去了

def brute_force2(remain_items, available_weight, item_sum):
    if len(remain_items) == 0:
        return 1
    elif available_weight == 0:
        return 1
    elif item_sum < available_weight:
        return 2**len(remain_items)
    else:
        item = remain_items[0]
        if item < available_weight:
            if item_sum - item < available_weight:
                return 2**len(remain_items[1:])
            else:
                return brute_force2(remain_items[1:], available_weight-item, item_sum-item) \
                       + brute_force2(remain_items[1:], available_weight, item_sum)
        else:
            return 1

完整代码如下：

line = input()
n = int(line.split(' ')[0])
w = int(line.split(' ')[1])
line = input()
v = []
for i in range(n):
    v.append(int(line.split(' ')[i]))

def brute_force(remain_items, available_weight):
    if len(remain_items) == 0:
        return 1
    elif available_weight == 0:
        return 1
    else:
        item = remain_items[0]
        if item < available_weight:
            return brute_force(remain_items[1:], available_weight-item) + brute_force(remain_items[1:], available_weight)
        else:
            return brute_force(remain_items[1:], available_weight)

def brute_force2(remain_items, available_weight, item_sum):
    if len(remain_items) == 0:
        return 1
    elif available_weight == 0:
        return 1
    elif item_sum < available_weight:
        return 2**len(remain_items)
    else:
        item = remain_items[0]
        if item < available_weight:
            if item_sum - item < available_weight:
                return 2**len(remain_items[1:])
            else:
                return brute_force2(remain_items[1:], available_weight-item, item_sum-item) \
                       + brute_force2(remain_items[1:], available_weight, item_sum)
        else:
            return 1


print(brute_force2(sorted(v), w, sum(v)))

发表于 2018-04-02 02:38:22 回复(7)

Hewitt

使用中途相遇法的思想。将30件物品分为两份，枚举第一份的所有取法，用一个体积数组记录体积和，再枚举第二份的所有取发，从体积数组中找到大于等于总体积-第二份体积的第一个位置，就是这个取法所贡献的答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 16;
int v[33];
long long A[1<<N];
int main(){
    int n,w;
    long long tot,ans=0;
    scanf("%d %d",&n,&w);
    for(int i=0;i<n;i++)scanf("%d",&v[i]);
    int up = n/2,down = n-n/2,tp,p=0;
    tp = 1<<up;
    for(int i=0;i<tp;i++){
        tot = 0;
        for(int j=0;j<up;j++)if(i&(1<<j))tot += v[j];
        A[p++] = tot;
    }
    sort(A,A+p);
    tp = 1<<down;
    for(int i=0;i<tp;i++){
        tot = 0;
        for(int j=0;j<down;j++)if(i&(1<<j))tot += v[j+up];
        tot = w-tot;
        if(tot>0)ans += upper_bound(A,A+p,tot)-A;
    }
    printf("%lld\n",ans);
}

编辑于 2020-07-21 18:08:03 回复(2)

Ga_li_dun_farming_guy

//如果所有物品加起来都没超过总重量，那么直接可以使用使用公式 nums = pow(2,n); //如果所有物品加起来没有超过总重量，这题由于总容量很大，不考虑动态规划。
//然而发现物品很少，不超过30个，那么考虑使用深搜。 代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
long long nums = 1;
void DFS(vector<long long>& array, int size , long long w, long long sum, int pos){
    if(sum <= w)
    {
        nums++;
        for(int i = pos + 1 ; i < size ; ++i)
        {
            DFS(array,size,w,sum+array[i],i);
        }
    }
}
int main()
{
    int n;
    long long  w;
    cin >>n >> w;
    long long total = 0;
    vector<long long > array(n,0);
    for(int i = 0 ; i != n ; ++i)
    {
        cin >> array[i];
        total += array[i];
    }
    if(total <= w)
    {
        nums = pow(2,n);
    }
    else
    {
        sort(array.begin(),array.end());
        for(int i = 0 ; i != n ; ++i)
            DFS(array, array.size(), w, array[i],i);
    }
    cout<<nums<<endl;
    return 0;
}

发表于 2018-03-31 13:18:38 回复(2)

果然多

在AC=80的代码中，在函数内部的开头加入

if sum(num)<=n2:

return 2**n1

即可通过

发表于 2019-10-31 23:02:30 回复(0)

逗比请来的猴子

/*
 * 参考大神的解题思路：https://www.nowcoder.com/profile/2156586/codeBookDetail?submissionId=23962584
 * 直接使用枚举的方式超时，使用递归
 *
 * 针对每个货物，有两种情况，不添加进背包或者添加进背包
 * */
public class Backup {
    private static int count = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            count = 0;
            int n = scanner.nextInt();
            int total = scanner.nextInt();
            int[] nums = new int[n];
            long sum = 0;
            for (int i = 0; i < n; i++) {
                nums[i] = scanner.nextInt();
                sum += nums[i];
            }
            if (sum <= total) {
                System.out.println((int)Math.pow(2, n));
            } else {
                dfs(0, 0, n, nums, total);
//            均不添加也是一种情况
                System.out.println(count + 1);
            }
        }
    }

    private static void dfs(long sum, int cur, int n, int[] nums, int total) {
        if (cur < n) {
            if (sum > total) {
                return;
            }
//            不添加这件零食
            dfs(sum, cur + 1, n, nums, total);
            //            当前这种添加方式合理,添加这件零食
            if (sum + nums[cur] <= total) {
                count++;
                dfs(sum + nums[cur], cur + 1, n, nums, total);
            }
        }
    }
}

发表于 2018-03-28 13:14:25 回复(5)

C/C++

nbgao


	
	
		#include <bits/stdc++.h>
using namespace std;
long cnt=0,w;
int n;
vector<long> v;

void DFS(long s, int p){
    if(s>w)
        return;
    cnt++;
    for(int i=p;i<n;i++)
        if(s+v[i]<=w)
            DFS(s+v[i], i+1);
}

int main(){
    long x,t=0;
    cin>>n>>w;
    for(int i=0;i<n;i++){
        cin>>x;
        v.push_back(x);
        t += x;
    }
    sort(v.begin(), v.end());
    if(t<=w)
        cout<<long(pow(2,n))<<endl;
    else{
        DFS(0, 0);
        cout<<cnt<<endl;
    }
    return 0;
}

发表于 2019-08-05 07:27:15 回复(0)

Java

咽喉上的刀

Java解答：利用的递归的思想。

import java.util.*;
 
public class Main {
    public static long result = 1;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        long w = input.nextInt();
        long[] v = new long[n];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            v[i] = input.nextInt();
            sum = sum + v[i];
        }
        if (sum <= w) {
            System.out.println((int) Math.pow(2, n));
        } else {
            state(v, 0, w, 0);
            System.out.println(result);
        }
    }
    public static void state(long[] v,int index, long w, long current){
        if (index == v.length)
            return;
        if (current + v[index] <= w){
            result++;
            state(v, index+1,w,current+v[index]);
        }
        state(v,index+1,w,current);
    }
}

发表于 2019-08-05 22:32:55 回复(0)

C/C++

kangjinci

首先w很大，所以01背包是解决不了了，只能考虑爆搜和状压dp

解法一：
//dfs + 剪枝,要是n = 40估计就过不了了
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;
using ll = long long;
const int N = 35;
ll a[N];

int n, w;
int ans;

void dfs(ll sum, int index) {
    if (sum > w) return;
    if (index == n) {
       ans++;
        return;
    }
    dfs(sum + a[index], index + 1);
    dfs(sum, index + 1);
}

int main() {
    cin >> n >> w;
    ll temp = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        temp += a[i];
    }
    if (temp <= w) {
        cout << (ll)pow(2, n) << endl;
        return 0;
    }
    sort(a, a + n);
    reverse(a, a + n);
    dfs(0, 0);
    cout << ans << endl;

    return 0;
}

解法二：
//用空间换时间，将前半部分的和用q[N]贮存起来,再对后半部分dfs，用二分查找符合条件的数目 (LeetCode 1775)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e6;
using ll = long long;

ll a[35];

ll q[N];

int cnt;
int n, w;
ll ans;

void dfs1(ll sum, int index) {
    if (sum > w) return;
    if (index == (n + 1) / 2) {
        q[cnt++] = sum;
        return;
    }
    dfs1(sum + a[index], index + 1);
    dfs1(sum, index + 1);
}

void dfs2(ll sum, int index) {
    if (sum > w) return;
    if (index == n) {
        ll j = (upper_bound(q, q + cnt, w - sum) - q); 
        ans += j;
        return;
    }
    dfs2(sum + a[index], index + 1);
    dfs2(sum, index + 1);
}

int main() {
    cin >> n >> w;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    dfs1(0, 0);
    sort(q, q + cnt);
    dfs2(0, (n + 1) / 2);
    cout << ans << endl;

    return 0;
}

解法三：状压dp
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
using ll = long long;

ll a[35];

int main() {
    ll n, w;
    cin >> n >> w;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int half = n / 2;
    int ls = half, rs = n - half;
    vector<ll> lsum(1 << ls), rsum(1 << rs);
    for (int i = 1; i < (1 << ls); ++i) {
        for (int j = 0; j < ls; ++j) {
            if ((i & (1 << j)) == 0) {
                continue;
            }
            lsum[i] = lsum[i - (1 << j)] + a[j];
            break;
        }
    }
    for (int i = 1; i < (1 << rs); ++i) {
        for (int j = 0; j < rs; ++j) {
            if ((i & (1 << j)) == 0) {
                continue;
            }
            rsum[i] = rsum[i - (1 << j)] + a[ls + j];
            break;
        }
    }
    sort(lsum.begin(), lsum.end());
    sort(rsum.begin(), rsum.end());

    ll ans = 0;
    for (int i = 0; i < lsum.size(); ++i) {
        ll j = (upper_bound(rsum.begin(), rsum.end(), w - lsum[i]) - rsum.begin());
        ans += j;
    }
    cout << ans << endl;

    return 0;
}

编辑于 2021-03-19 20:39:29 回复(0)

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)

Java

此用户已被注销

利用回溯算法思想解决背包问题。（递归穷举+剪枝）

import java.util.*;
public class Main{
    static int res = 0;//种类计数
    //n:零食的数量
    //w:背包的容量
    //v:每袋零食的体积
    //i:考虑到第几个零食了
    //cw:目前背包内已有的零食总重（必须定义为long，否则求和溢出，AC80%）
    public static void solution(int n,int w,int[] v,int i,long cw){
        //回溯算法思想
        if(i<n){  //未全部考虑完
            solution(n,w,v,i+1,cw);//不放当前i的零食，直接考虑i+1
            if(cw+v[i]<=w){ //放当前i的零食
                res++;
                solution(n,w,v,i+1,cw+v[i]);
            }
        }
        
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int w = scanner.nextInt();
        int[] v = new int[n];
        long sum = 0;
        for(int i=0;i<n;i++){
            v[i]=scanner.nextInt();
            sum=sum+v[i];
        }
        if(sum<=w) 
            System.out.println((int)Math.pow(2,n));
        else{
            solution(n,w,v,0,0);
            System.out.println(res+1);
        }
    }
}

编辑于 2019-08-17 19:35:07 回复(1)

C/C++

ElonB

/*
Deep-First Search
总体积sum_v小于等于背包容量w ,计数cnt++
从当前t向后遍历放入情况，dfs(i+1)
所有遍历完成，cnt即为所求
*/
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 100000
long n, w, v[30], cnt = 0, sum_v = 0;

void dfs(int t)
{
    if(sum_v <= w) {
        cnt++;
    } else return;
    if(t >= n) return;
    for(int i = t; i < n; i++) {
        sum_v += v[i];
        dfs(i + 1);
        sum_v -= v[i];
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    cin >> n >> w;
    long sum_t = 0;
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        sum_t += v[i];
    }
    sort(v, v + n, greater<long>());
    if (sum_t <= w) {
        cnt = pow(2, n);
    } else {
        dfs(0);
    }
    cout << cnt << endl;
    return 0;
}

编辑于 2019-07-03 11:38:37 回复(0)

若相熙

import java.util.Scanner;

public class Main {
    public static long result = 1;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long total = scanner.nextLong();
        long[] base = new long[n];
        for (int i = 0; i < base.length; i++) {
            base[i] = scanner.nextLong();
        }
        dfs(base, 0, total, 0);
        System.out.println(result);
        
    }
    
    public static void dfs(long[] base, int index, long total, long current) {
        if(index == base.length) {
            return;
        }
        if(current + base[index] <= total) {
            result++;
            dfs(base, index + 1, total, current  + base[index]);
        }
        dfs(base, index + 1, total, current);
    }
}

发表于 2018-04-13 19:35:06 回复(0)

霍七

本套8道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long int w;
void DFS(long long int *data, int n, int index, long long int weight, vector<long long int> &result);
int main()
{
    int n; cin >> n >> w;
    long long int *data = new long long int[n];
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    vector<long long int> part1;
    vector<long long int> part2;
    DFS(data, n / 2, 0, 0, part1);
    DFS(data + n / 2, n - n / 2, 0, 0, part2);
    sort(part1.begin(), part1.end());
    sort(part2.begin(), part2.end());
    int count = 0, j = part2.size() - 1;
    for (int i = 0; i < part1.size(); i++) {
        while (j >= 0) {
            if (part1[i] + part2[j] <= w) {
                count += j + 1;
                break;
            }
            j--;
        }
    }
    cout << count;
    delete[] data;
    return 0;
}
void DFS(long long int *data, int n, int index, long long int weight, vector<long long int> &result)
{
    if (weight > w) {
        return;
    }
    if (index == n) {
        result.push_back(weight);
        return;
    }
    DFS(data, n, index + 1, weight, result);
    DFS(data, n, index + 1, weight + data[index], result);
}

发表于 2018-03-28 19:16:28 回复(1)

弹琴复长啸

动态规划，递归解决

要点：相同重量的零食要合并，结合排列组合降低时间复杂度

上代码

import java.util.Scanner;
import java.util.HashMap;
import java.math.BigInteger;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        int w = Integer.parseInt(str1.split(" ")[1]);
        String[] strs = str2.split(" ");
 
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < strs.length; i ++) {
            int key = Integer.parseInt(strs[i]);
            int val = map.get(key) == null ? 0 : map.get(key);
            map.put(key, val + 1);
        }
 
        int[][] v = new int[map.size()][2];
        int i = 0;
        for(Integer key : map.keySet()) {
            v[i][0] = key;
            v[i][1] = map.get(key);
            i++;
        }
        System.out.println(dp(v, 0, 0, w));
    }
 
    private static long dp(int[][] v, int pos, long wCur, long w) {
        if(pos >= v.length) {
            return 1;
        }
 
        int r = 0;
        for(int i = 0; i <= v[pos][1]; i++) {
            if(wCur + v[pos][0] * i <= w) {
                long factor = i > 0 ? c(i, v[pos][1]) : 1;
                r += dp(v, pos + 1, wCur + v[pos][0] * i, w) * factor;
            }
        }
        return r;
    }
     
    private static long c(int x, int y) {
        BigInteger r = BigInteger.valueOf(1);
        for(int i = 0; i < x; i++) {
            r = r.multiply(BigInteger.valueOf(y - i));
        }
        for(int i = 0; i < x; i++) {
            r = r.divide(BigInteger.valueOf(i + 1));
        }
        return r.longValue();
    }
}

发表于 2020-06-01 10:14:23 回复(0)

子明同学

注意：由于背包容量可以取得很大，所以不能使用动态规划，否则会内存溢出

#include<algorithm>
using namespace std;
void deep(int index, long long sum, int& count, int* v, int w, int n) {
    if (index < n) {
        if (sum > w) return;
        deep(index + 1, sum, count, v, w, n);
        if (sum + v[index] <= w) {
            sum += v[index];
            count++;
            deep(index + 1, sum, count, v, w, n);
        }
    }
}

int main() {
    static int count = 0; //保存零食放法
    int n, w;
    cin >> n >> w;
    int v[30]{0};
    long long sum = 0; //当前总体积
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        sum += v[i];
    }
    if (sum <= w) { //如果当前总体积小于背包容量，则直接计算
        cout << static_cast<int>(pow(2, n));
    }
    else {
        deep(0, 0, count, v, w, n);
        cout << count+1; //什么零食都不放也是一种放法
    }
    return 0;
}

发表于 2020-05-05 23:12:37 回复(0)

gywy

用数组进行DP会爆空间，所以考虑DFS+剪枝的写法。同时参考讨论区的做法，先特判再进行DFS

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 35;
LL v[N];
int n, m;
int ans;

void dfs(int u, LL vol)
{
  if (vol > m) return;

  if (u == n)
  {
    ans ++;
    return;
  }

  // 选择第u个物品
  dfs(u + 1, vol + v[u]);

  // 不选第u个物品
  dfs(u + 1, vol);

}

LL power2(int x)
{
    LL res = 1;
    for (int i = 0; i < x; i ++) res *= 2;
    return res;
}

int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i ++) cin >> v[i];
  LL tmp = 0;
  for (int i = 0; i < n; i ++) tmp += v[i];
  if (tmp <= m)
  {
      cout << power2(n) << endl;
      return 0;
  }
  sort(v, v + n);
  reverse(v, v + n);
  dfs(0, 0);
  cout << ans << endl;
  return 0;
}

编辑于 2020-03-15 22:06:05 回复(0)

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)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师穷举网易高级算法 2019 Java工程师

来自：网易2019实习生招聘...

上传者：小小

难度：

105条回答 317收藏 30241浏览

通过挑战的用户

查看代码

LZY2024

2023-02-23 20:04:15
牛客36477...

2022-10-21 20:02:19
ChiliChili

2022-09-03 20:47:16
前端学习中

2022-08-27 19:10:50
upye666

2022-08-20 13:39:33

牛牛的背包问题

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题