牛牛的背包问题

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

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

算法知识视频讲解

Roee

python3代码,DFS去遍历

def wx(v, x):
    return sum([v[i] * x[i] for i in range(len(v))])

def dfs(v, p, f, x, w):
    if p == len(v) - 1:
        k = wx(v, x + [f])
        if k > w:
            return 0
        else:
            return 1
    temp = wx(v, (x+[f]+[0]*len(v))[:len(v)])
    if temp > w:
        return 0
    elif temp == w:
        return 1
    else:
        return dfs(v, p+1, 0, x+[f], w) + dfs(v, p+1, 1, x+[f], w)

n, w = list(map(int, input().split()))
v = sorted(list(map(int, input().split())))
v.reverse()
if sum(v) <= w:
    print(2**n)
else:
    print(dfs(v, 0, 0, [], w) + dfs(v, 0, 1, [], w))

发表于 2018-08-10 02:54:36 回复(0)

Java

求offer砸到我

import java.util.*;
public class Main{
  
   static long w;
   static long ans=0;//计数器
   static long sum=0;
   static  int n;
   static int[] weight;
    public static void main(String[] args) {

        
       Scanner sc=new Scanner(System.in);
       n=sc.nextInt();//物品的件数
       w=sc.nextInt();//背包的体积
        weight=new int[n];
        for(int i=0;i<n;i++){
//            存储物品的体积
            weight[i]=sc.nextInt();
            sum+=weight[i];
        }
//        如果背包能全部存下物品
        if(sum<w){
            ans =(int)Math.pow(2,n);
        }else{
            Arrays.sort(weight);
            dfs(0,0);
        }
        System.out.println(ans);


    }
    public static void dfs(long  sum,int index){
        if(sum>w)
            return;
        if(sum<w)
            ans++;
        for(int i=index;i<n;i++){
            dfs(sum+weight[i],i+1);
        }
    }
}

发表于 2019-09-05 13:26:55 回复(0)

jieg

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

case通过率为80.00%

import java.util.Scanner;
public class Main {
    private static int cnt = 1;
    private static int[] v;
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int w = s.nextInt();
        v = new int[n];
        for (int i = 0; i < n; i++) {
            v[i] = s.nextInt();
        }
        search(w, 0);
        System.out.println(cnt);
    }
    public static void search(int w, int i) {
        if (i >= v.length) {
            return;
        }
        if (v[i] <= w) {
            cnt++;
            search(w - v[i], i + 1);
        }
        search(w, i + 1);
    }
}

发表于 2019-05-03 20:27:13 回复(0)