【Java】牛牛的背包问题

小灰灰 2024-04-17 21:52 72阅读 0赞

**题目描述**

牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为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种情况。

package 牛客;
    
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    
    public class 牛牛的背包问题 {
        
        public static void main(String[] args) throws Exception{
        
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] str = br.readLine().split(" ");
            int n = Integer.parseInt(str[0]); // n
            long w = Long.valueOf(str[1]); // w
            long[] v = new long[n]; // v[i]
            str = br.readLine().split(" ");
            long sum=0;
            for(int i=0;i<n;i++){
        
                v[i] = Long.valueOf(str[i]);
                sum += v[i];
            }
            if (sum <= w) {
        
                System.out.println((long)Math.pow(2, n));
                return;
            }
            System.out.println(randell(v,n-1,w));
        }
    
        private static int randell(long[] v, int i, long w) {
        
            if (i == 0) {
        
                if (v[i] <= w) {
        
                    return 2;//放入，不放入
                } else {
        
                    return 1;//不放入
                }
            }
            if (w == 0) {
        
                return 1;//不放入
            }
            if (v[i] <= w) {
        
                return randell(v,i-1,w-v[i])+randell(v,i-1,w);
            } else {
        
                return randell(v,i-1,w);
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/6cbd1aba20be49bb92e1d4163990c6c5.png