【动态规划】数字组合

题目

278. 数字组合 - AcWing题库

---

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

输入格式

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

第二行包含 $N$ 个整数，表示 $A_1,A_2,…,A_N$ 。

输出格式

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

数据范围

$1 \le N \le 100$ ,
$1 \le M \le 10000$ ,
$1 \le A_i \le 1000$ ,
答案保证在 int 范围内。

输入样例：

4 4
1 1 2 2

输出样例：

3

解题

方法一：动态规划

思路

本题是：01背包问题的应用：01背包问题求方案数。

思维过程

动态规划

• 状态定义：$f[i][j]$ 表示所有只考虑前 $i$ 个数字，求和恰好为 $j$ 的所有选法数量。

• 状态转移方程：$f[i][j] = \begin{cases} f[i-1][j] \\ f[i-1][j] + f[i-1][j-v[i]] & v[i] \le j \\ \end{cases}$

• 初始状态：

  • 只考虑前 $0$ 个数字，求和恰好为 $0$ 时，空集是一种方案，故：$f[0][0] = 1$ ；
  • 只考虑前 $0$ 个数字，求和恰好为 $1 \dots j$ 时，没有任何方案，故：$f[0][1 \dots j] = 0$ 。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int c = (int) in.nval;
        int[] v = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            v[i] = (int) in.nval;
        }
        int[][] f = new int[n + 1][c + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= c; ++j) {
                f[i][j] = f[i - 1][j];
                if (v[i] <= j) f[i][j] += f[i - 1][j - v[i]];
            }
        }
        System.out.println(f[n][c]);
    }
}

滚动数组优化：

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int c = (int) in.nval;
        int[] f = new int[c + 1];
        f[0] = 1;
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            int v = (int) in.nval;
            for (int j = c; j >= v; --j) {
                f[j] += f[j - v];
            }
        }
        System.out.println(f[c]);
    }
}

#include <iostream>

using namespace std;

const int N = 10010;
int n, m;
int f[N];

int main() {
    scanf("%d%d", &n, &m);
    f[0] = 1;
    for (int i = 0; i < n; ++i) {
        int x; scanf("%d", &x);
        for (int j = m; j >= x; --j) {
            f[j] += f[j - x];
        }
    }
    printf("%d\n", f[m]);

    return 0;
}