题目内容：https://www.luogu.com.cn/problem/P1164

主要算法：(0-1背包问题)动态规划

对0-1背包问题理解：

1、典型题目：给定𝑛个物品，第𝑖个物品的重量为𝑤[ i ]、价值为𝑣[ i ]，和一个容量为 cap 的背包。每个物品只能选择一次，问在限定背包容量下能放入物品的最大价值。

2、dp数组含义：dp[ i, c ] 表示前i个物品在容量为c的背包中的最大价值

3、状态转移方程：

不放入物品𝑖：背包容量不变，状态变化为[i−1,𝑐]；

放入物品𝑖：背包容量减少w[i]，价值增加v[i]，状态变化为[i-1,𝑐−w[i]]。

        dp[i, c] = max( dp[ i-1, c ], dp[ i-1, c-w [i] ] + v[i]  )，

dp[ i-1, c ] 表示不放入第 i 个物品，dp[ i-1, c-w [i] ] + v[i] 表示放入第 i 个物品; 

4、正序循环，填充dp表

5、一维数组进行空间优化逆序循环(如果采取正序遍历，那么遍历到𝑑𝑝[𝑖,𝑗]时，左上方𝑑𝑝[𝑖−1,1]~𝑑𝑝[𝑖−1,𝑗−1]值可能已经被覆盖，此时就无法得到正确的状态转移结果)

        dp[c] = max( dp[ c ], dp[ c-w[i] ]+v[i] )

本题实现思路：

1、菜品种类指代 物品种类；钱指代背包容量

2、需要求的是方案数，而不是最佳方案

Java代码：

import java.io.*;

//动态规划-背包
public class P1164 {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int n, m;

    public static void main(String[] args) throws IOException {
        n = nextInt();  //菜品种类
        m = nextInt();  //钱
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();   //每一个物品对应的钱
        }
        int[] dp = new int[m + 1];
        dp[0] = 1; // 初始状态：花费0元有1种方案

        for (int i = 0; i < n; i++) {   //当前菜品的金额
            for (int j = m; j >= 1; j--) {   //倒序进行状态转移
                if (a[i]<=j)
                    dp[j] += dp[j - a[i]];  // 不选择当前菜品+选择当前菜品
            }
        }

        System.out.println(dp[m]);
    }

    static int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}