首页 > 试题广场 > 牛牛的背包问题
[编程题]牛牛的背包问题
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为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种情况。
问题描述
                       
                        
其中,表示第i个放入还是不放入,设state(i,w)表示i个零食放入背包小于等于W的个数,把state(i,w)分解,可以分解为两个情况:
1、是第i个不放入时,前i-1个零食放入背包小于等于W的个数即state(i-1,w);
2、是在第i个放入的情况下,前i-1个零食放入背包体积小于等于W-v[i]的个数即state(i-1,w-v[i]);
即               state(i,w) = state(i-1,w) + state(i-1,w-v[i])
边界条件:i = 1时,state(1,w1) 此时如果w1 >0 且v[1]<=w1,state(1,w1) = 2,即有可放入和不放入两种;
                  i = 1 时,swate(1,w1)此时如果w1 >0且v[1] > w1,state(1,w1)=1,即只有不放入一种;
                  如果state(i,w)中出现w<=0,则state(i,w)=0;
例子:零食体积1 2 4,w=10
            则 state(3,10) = state(2,10) + state(2,6)
                                   = state(1,10) + state(1,8) + state(1,6) + state(1,4)
                                   = 2 + 2 + 2 + 2 = 8
采用递归解法:AC率80%
#include<iostream>
#include<vector>
using namespace std;

int f(int n1, int n2,vector<int> &num)
{
    if(n2 <= 0)
    {
      return 0;
    }
    if(n1 == 1)
    {
        if(num[n1] <= n2)
        {
            return 2;
        }
        else
        {
            return 1;
        }
    }
    return f(n1-1,n2,num) + f(n1 - 1,n2-num[n1],num);
}
int main()
{
    int n1,sum;
    cin >> n1 >> sum;
    vector<int> res(n1 + 1);
    for(int i=1;i<=n1;i++)
    {
        cin >> res[i];
    }
    cout << f(n1,sum,res) << endl;                          
    return 0;
}

发表于 2018-03-28 18:31:39 回复(4)
/*前几个答案的递归是有问题的,在调用的时候不需要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 回复(9)

这道题采用最基本的递归做法的话,每一个物品都要考虑放入或者不放入两个情况,算法复杂度为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 回复(3)
//如果所有物品加起来都没超过总重量,那么直接可以使用使用公式 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)
这一类背包问题有两种方法,一种是当物品个数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 回复(1)
使用中途相遇法的思想。将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 += lower_bound(A,A+p,tot)-A;
    }
    printf("%lld\n",ans);
}

发表于 2019-06-28 11:35:27 回复(1)
/*
 * 参考大神的解题思路: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)
/*
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.*;
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 回复(0)
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)
#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)
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 回复(3)
def dfs(a,n,index,weight,w,result):
    if weight>w:
        return
    if index==n:
        result.append(weight)
        return
    dfs(a,n,index+1,weight,w,result)
    dfs(a,n,index+1,weight+a[index],w,result)
if __name__=='__main__':
    import sys
    line1=input().split()
    n,w=int(line1[0]),int(line1[1])
    ss=sys.stdin.readline().strip()
    while not ss:
        ss=sys.stdin.readline().strip()
    a=[int(ab) for ab in ss.strip().split()]
    r1=[]
    r2=[]
    dfs(a,n//2,0,0,w,r1)
    dfs(a[n//2:],n-n//2,0,0,w,r2)
    r1.sort()
    r2.sort()
    count=0
    j=len(r2)-1
    for i in range(len(r1)):
        while j>=0:
            if r1[i]+r2[j]<=w:
                count+=j+1
                break
            j-=1
    print(count)

发表于 2018-08-13 20:06:56 回复(1)
#include<bits/stdc++.h>
using namespace std;
long long n,w,v[50],ans=0;
long long Pow(long long a,long long b)    //快速幂
{
    long long r=1;
    while(b)
    {
        if(b&1)
            r*=a;
        a*=a;
        b>>=1;
    }
    return r;
}
void dfs(long long m,long long s)   //放m号,之前体积为s
{
    if(s>w)
        return ;
    if(m==n)
    {
        ans++;
        return ;
    }
    dfs(m+1,s+v[m]);    //下次放m+1号,之前体积为s+v[m]
    dfs(m+1,s);
    return ;
}
int main()
{
    long long i;
    long long sum=0;
    cin>>n>>w;    //数量和背包的容量
    for(i=0;i<n;i++)
    {
        cin>>v[i];
        sum+=v[i];
    }
    if(sum<=w)
        cout<<Pow(2,n)<<endl;
    else
    {
        dfs(0,0);   //下次放0号,之前体积为0
        cout<<ans<<endl;
    }
    return 0;
}
如果不用判断总数会80%答案正确,因为超时
这个代码算是比较简单的啦
发表于 2018-05-31 23:20:22 回复(0)
//因为n很小,w很大。所以可以考虑每个元素,元素有两种状态放与不放,用递归可以很轻松的实现。
//边界条件是i>n,i是元素下标,n是总的元素各数。或者当前递归内背包体积re大于最大体积w。
//每次递归如果当前递归内背包体积re小与最大体积w,方法数加一。
//注意要先将v[]数组排好序。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n;
long w;
long v[35];
int result = 1;
void dfs(int i, int falg, long re)
{
    if (i >= n || re>w)
    {
        return;
    }
    if (falg==1)
    {
        re += v[i];
        if (re <= w)
        {
            result++;
        }
    }
    dfs(i + 1, 1, re);
    dfs(i + 1, 0, re);
}
int main()
{
    cin >> n >> w;

    long allV = 0;
    for (int i = 0; i<n; i++)
    {
        cin >> v[i];
        allV += v[i];
    }
    if (allV <= w)
    {
        while (n--)
        {
            result *= 2;
        }
    }
    else
    {
        sort(&v[0], &v[n - 1]);
        dfs(0, 1, 0);
        dfs(0, 0, 0);
    }
    cout << result;
    return 0;
}

发表于 2018-05-08 20:08:00 回复(0)
/*
对v[i]排序,求小于w的最小和的长度k;
k即为最多可选种数,然后dfs(k)即可,注意把0体积这种加上
当k==n的时候,种数即为2的n次方,此时如果dfs会卡80%
*/
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int v[60],vis[60],d[60];
int cnum,n,w,ll;
int dfs(int u,int dd,int kk){     if(u==0){
//        for(int i=0;i<ll;i++)cout << d[i] <<" ";
//        cout << "dd"<<dd<<" "<<cnum<<"\n";         return 0;     }     else{         for(int i=kk;i<n;i++)         if(vis[i]==0&&(dd+v[i])>=0&&(dd+v[i])<=w){             vis[i]=1;//d[ll++]=v[i];             cnum++;             dfs(u-1,dd+v[i],i);             vis[i]=0;//ll--;         }     }     return 0;
}
int main()
{     cin >> n >> w;     for(int i=0;i<n;i++)cin >> v[i];     sort(v,v+n);     int k=0;     long long min=v[0];     for(k=1;k<=n;k++){         if(min>w)break;         min+=v[k];     }     k--;cnum=0;     memset(vis,0,sizeof(vis));     int ans=1;     if(k==n)ans=pow(2,n);     else{         dfs(k,0,0);         ans+=cnum;
    }     cout << ans <<"\n";     return 0;
}

发表于 2018-04-27 16:11:41 回复(0)
#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    int n,w;
    scanf("%d%d",&n,&w);
    vector<int> arr(n);
    int nums = 1;
    int sum = w;
    for(int i=0;i<n;++i){
        scanf("%d",&arr[i]);
        if(sum >=0) //防止负向溢出判断;若不加判断则需要将sum类型设置为long long
            sum -= arr[i];
    }
    if(sum >= 0)
        nums = pow(2,n);
    else{
        sort(arr.begin(),arr.end());
        stack<pair<int,int>> weight; //深度优先搜索,也可以宽度优先搜索(直接将栈换成队列就可以了)
        weight.emplace(-1,w);

        while(!weight.empty()){
            auto now = weight.top();
            weight.pop();
            for(int i=now.first+1;i<n && now.second>=arr[i];++i){
                nums++;
                //使用递减方式,而不是增加的方式来判断能否装进背包,减少内存使用
                weight.emplace(i,now.second-arr[i]);
            }
        }
    }
    cout << nums << endl;
    return 0;
}

发表于 2018-04-12 16:28:16 回复(0)
//哪里错了,找不到问题

import java.util.Scanner;

public class FC {
    static  int num=0;
    static  int weight=0;
    static int  v;
    public static void main(String[] args) {
        int n;
         
        int put[];
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        put = new int[n];
        v=scanner.nextInt();
        for (int i = 0; i < put.length; i++) {
            put[i] = scanner.nextInt();
        }
        isput(put, 0);
        
        System.out.println(num);
    }
    
    static  void isput(int a[],int index){
        if(weight>v)
            return;
        if(index==a.length){
            num++;
            return;
        }
        isput(a, index+1);
        weight+=a[index];
        isput(a, index+1);
        weight-=a[index];
         
        
        
    }
}

发表于 2018-04-01 19:41:08 回复(2)

热门推荐

通过挑战的用户

查看代码