首页 > 试题广场 >

牛牛的背包问题

[编程题]牛牛的背包问题
  • 热度指数：48007 时间限制：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)
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)
小新没有蜡笔~头像 小新没有蜡笔~
比较经典的动态规划问题
使用一个二维数组dp[n][w]，其中dp[i][j]表示：前i个零食，放入容量为j的背包的放法数量
对“前i个零食，放入容量为j的背包”，进行分类讨论
  1. 第j个零食不放入背包，放法数量为dp[i-1][j]
  2. 第j个零食放入背包，放法数量为dp[i-1][j-volumn[i]]+1，其中volumn[i]表示第i个零食的体积
所以dp[i][j]=dp[i-1][j]+dp[i-1][j-volumn[i]]+1
最终的结果为dp[n][w]+1，加一是为了加上“背包中什么都不放”这一种放法
对于dp[][]进行初始化时，将第0行和第0列初始化为0

运行结果如下，检查了很多次代码，试了一些特殊样例，也没有发现代码的问题，望大家不吝赐教 
您的代码已保存
请检查是否存在数组越界等非法访问情况点击对比用例标准输出与你的输出
case通过率为20.00%

代码如下： 
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int w = in.nextInt();
		if (n < 1 || w < 1) {
			System.out.println(0);
			return;
		}
		int[] arr = new int[n + 1];
		for (int i = 1; i < n + 1; i++) {
			arr[i] = in.nextInt();
		}
		int[][] dp = new int[n + 1][w + 1];

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= w; j++) {
				int num1 = j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] + 1 : 0;// 在容量为j的背包中，放入第i个零食时，零食的放法数量
				int num2 = dp[i - 1][j];// 在容量为j的背包中，不放入第i个零食时，零食的放法数量
				dp[i][j] = num1 + num2;
			}
		}
		System.out.println(dp[n][w] + 1);
	
	}
}




编辑于 2020-02-21 16:13:58 回复(5)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

牛牛的背包问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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