神奇的口袋

神奇的口袋

解析

一道典型的动态规划问题，首先说明下，面对一个物品的时候，你能做的选择只有两个：选or不选，那么选不选的标准是什么呢？很简单，就是看选了之后对你的最终的目的有什么影响，如果是正的影响，那就选；如果是负的影响，就不选。对于这道题同样也是。

我们先用一个数组arr表示物品的体积，然后设置一个变量count，表示选择物品的方式数目，给他添加两个参数：i和s，分别表示下面的意思：

i: 表示你目前面对的物品的编号
s: 面对i号物品时的背包剩余容量
count(i,s)表示，面对i号物品时且你的背包容量为s时的选择方法数

举个栗子：
在本题中，我们需要求的是当背包容量为40时，面对3号物品时，你有多少种选择方式（也可以从1号开始选）。即我们要求的是count(3,40)。那么选或者不选的示例图如下：

分析

抽象出如下的递归表达式：

选第i件物品：count(arr,i,s)=count(arr, i - 1, s - arr[i])
不选第i件物品：count(arr,i,s)=count(arr, i - 1, s)

那么出口条件是什么呢？有以下几个：

1. 当s==0时，就说明满足条件了，返回1
2. 当i==1时，如果arr[i]恰好等于背包剩余空间s，满足条件，返回1；如果arr[i]不等于剩余背包空间，返回0；
3. 这个条件比较隐秘，如果第i个物品的容量arr[i]大于背包剩余空间，即arr[i]>s时，我们就可以不用考虑拿这件物品这个选择了，因为根本拿不动，所以这是只要返回不拿该物品的选择就可以了，即 return count(arr,i-1,s)

最后将选第i件物品和不选第i件物品的方法数想加即为最终的结果了。

代码如下

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(count(a, n, 40));
    }

    static int count(int[] arr, int i, int s) {
        if (s == 0) return 1;
        else if (i == 1) {
            if (arr[i] == s) return 1;
            else return 0;
        } else if (arr[i] > s)
            return count(arr, i - 1, s);
        else return count(arr, i - 1, s - arr[i]) + count(arr, i - 1, s);
    }
}