文章目录

题目来源题目描述解题思路-递归实现`main()`部分实现方法`count(int n，int s)`部分 实现代码

题目来源

https://www.nowcoder.com/questionTerminal/9aaea0b82623466a8b29a9f1a00b5d35

题目描述

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

输入描述: 输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

输出描述: 输出不同的选择物品的方式的数目。

示例1 输入 3 20 20 20 输出 3

解题思路-递归实现

main()部分

取得物体的数目和每个物体的体积 需要有一个整形变量n接收物体的数目。需要有一个整形数组int[] array;接收每个物体的体积。

实现方法count(int n，int s)部分

从数组的最后一件物品array[n-1]倒着装。有两种结果：

装最后一件物品。 则剩余可装 n-1件物品，剩余 s-array[n-1] 可装物品的体积count( n-1,s-array[n-1]) 不装最后一件物品。 则剩余可装 n-1件物品，剩余 s可装物品的体积count(n-1,s)

递归出口

如果剩余可装物品的体积s==0，则不再递归。 或者已经装完所有物品，还是没有装满给的体积，则不再递归。

实现代码

import java.util.*; public class Title1{ static int[] array = new int[20]; //数组长度设置为20即可 /** *从后往前倒着装 * @param n 当前物品件数 * @param s 当前剩余可放物品的体积 * @return */ public static int count(int n,int s){ //出口 if (s == 0) { //当前容量为0,不装 1种方法 return 1; } if (n <=0) { //如果都装到数组的最后还没有装满，则装不满，返回0 return 0; } //2.选第n个和不选第n个两种结果 return count(n-1,s-array[n-1]) + count(n-1,s); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); //1.物品件数 for (int i = 0; i < n; i++) { array[i] = sc.nextInt(); } int s = 40; //初始化可放物品体积为40 System.out.println(count(n,s)); } }