$$\color{Red}{数字组合:01背包求方案数}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

输入格式

第一行包含两个整数 N 和 M。

第二行包含 N 个整数，表示 A1,A2,…,AN。

输出格式

包含一个整数，表示可选方案数。

数据范围

1 ≤ N ≤ 100

1 ≤ M ≤ 10000

1 ≤ Ai ≤ 1000

答案保证在 int 范围内。

输入样例：

4 4
1 1 2 2

输出样例：

3

证明

java优化二维

import java.io.*;

public class Main {
    static int N = 110, n, m;
    static int f[][] = new int[N][N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        String s2[] = br.readLine().split(" ");

        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int x = Integer.parseInt(s2[i - 1]);
            for (int j = 0; j <= m; j++) {
                f[i][j] = f[i - 1][j];
                if (j >= x)
                    f[i][j] += f[i - 1][j - x];
            }
        }

        System.out.println(f[n][m]);
    }
}

java优化一维

import java.io.*;

public class Main {
    static int N = 10010, n, m;
    static int f[] = new int[N];


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1[] = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        String s2[] = br.readLine().split(" ");

        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            int x = Integer.parseInt(s2[i - 1]);
            for (int j = m; j >= x; j--)
                f[j] += f[j - x];
        }

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

python

f = [0] * 10010
n, m = map(int, input().split())
a = [int(x) for x in input().split()]

f[0] = 1
for i in range(n):
    for j in range(m, a[i] - 1, -1):
        f[j] += f[j - a[i]]

print(f[m])