编程题：神奇的口袋

忘是亡心i 2023-07-12 03:49 11阅读 0赞

### 文章目录 ###

*   *  问题描述：
     *  解题思路：
     *  解题代码：

链接： [神奇的口袋][Link 1]  
来源：牛客网

## 问题描述： ##

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

## 解题思路： ##

分析题意：往书包里装东西从最后一个开始装：
    此为第一种情况：
       可能的情况是最后一个就是40，剩余空间为0；
       或者是最后一个一直往前直到装到某一个的时候装不下了；
       再者就是从第二条开始装着装着发现装完了。
    然后后续的情况就是从倒数第二个开始装一直循环第一种的装法，直到最后一个
    
    分析可得我们可以用递归的手法来解决这个问题

## 解题代码： ##

import java.util.Scanner;
    
    public class Main1 { 
        static int count=0;//表示有多少种
        static int[] arr; //表示口袋
        static int n;//表示物品的种类
        public static void main(String[] args) { 
            Scanner input=new Scanner(System.in);
            while(input.hasNext()){ 
                n=input.nextInt();
                arr=new int[n+1];
                /*这里的大小我们设置的比物品的种类要大1，因为在下边进行递归的时候， 如果大小为n,因为在放第一个的时候还要考虑第一个的前一个（倒着放的：相对正着放方便一点）， 数组大小为n的话会造成数组溢出 */
                for(int i=1;i<=n;i++){ 
                    arr[i]=input.nextInt();
                }
            }
            count(40,n);
            System.out.println(count);
        }
        public static void count(int s,int n){ 
            /** * s表示背包剩下的容量大小 * n表示剩下的东西数量 */
            //如果背包容量刚好等于零，说明刚好装满
            if(s==0){ 
                count++;
            }
            //背包容量小于零或者容量大于零但是东西数量小于零，则不能刚好装满（也就是要么装不下了要么不够装了）
            if(s<=0||(s>0&&n<0)){ 
                return ;
            }
            //从最后一个开始装
            count(s-arr[n],n-1);
            //如果最后一个和其他是都值完了，从倒数第二个开始
            count(s,n-1);
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/9aaea0b82623466a8b29a9f1a00b5d35
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306213255989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4,size_16,color_FFFFFF,t_70