首页 > 试题广场 >

牛牛的背包问题

[编程题]牛牛的背包问题
  • 热度指数：47659 时间限制：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种情况。
算法知识视频讲解
添加回答
lewis_c++头像 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头像 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头像 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头像 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头像 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头像 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)
C/C++
kangjinci头像 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头像 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头像 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)
come听风吹雨头像 come听风吹雨
求助各位大佬，动态规划为何只通过百分之二十啊 
import java.util.*;
public class Main{
    public static void main(String[] args){
        int sum=0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        int[] v = new int[n];
        int i,j;
        
        for(i=0;i<n;i++)
            v[i] = sc.nextInt();
        int[][] dp = new int[n+1][];
        for(i=0;i<=n;i++)
            dp[i] = new int[w+1];
        for(i=0;i<=n;i++)
            dp[i][0] = 0;
        for(j=0;j<=w;j++)
            dp[0][j] = 1;
        for(i=1;i<=n;i++){
            for(j=1;j<=w;j++){
                if(j>=v[i-1])
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-v[i-1]];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        System.out.println(dp[n][w]);
        
    }
}

编辑于 2020-02-25 14:16:19 回复(3)
hanzz1头像 hanzz1
利用回溯法穷举 
#include <iostream>
(720)#include <vector>
#include <cmath>

class putSnacks
{
public:
    putSnacks(int _n,int _w):w(_w),cnt(1),sum(0)
    {
        long snack;
        long _sum = 0;
        for (int i=0;i<_n;i++)
        {
            std::cin >> snack;
            snacks.push_back(snack);
            _sum += snack;
        }
        if (_sum <= w) cnt=pow(2,_n);//总和小于容量
    }
    
    int solution()
    {
        if (cnt==1) solution(0);
        return cnt;
    }
    
private:
    std::vector<long> snacks;
    int w,cnt;
    long sum;
    void solution(int pos)
    {
        //每次只放入第i个以后的零食，避免重复
        for(int i=pos;i<snacks.size();i++)
        {
            sum = snacks[i]+sum;
            if (sum==w)
            {
                cnt++;
            }
            else if (sum<w)
            {
                cnt++;
                solution(i+1);
            }
            sum = sum - snacks[i];
        }
    }
};

int main()
{
    int n,w;
    std::cin >> n >> w;
    putSnacks res(n,w);
    std::cout << res.solution() << std::endl;
    return 0;
}

发表于 2020-02-22 22:30:33 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

牛牛的背包问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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