侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【动态规划】数字组合

GabrielxD
2023-02-17 / 0 评论 / 0 点赞 / 115 阅读 / 736 字
温馨提示:
本文最后更新于 2023-05-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

278. 数字组合 - AcWing题库


给定 NN 个正整数 A1,A2,,ANA_1,A_2,…,A_N ,从中选出若干个数,使它们的和为 MM ,求有多少种选择方案。

输入格式

第一行包含两个整数 NNMM

第二行包含 NN 个整数,表示 A1,A2,,ANA_1,A_2,…,A_N

输出格式

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

数据范围

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

输入样例:

4 4
1 1 2 2

输出样例:

3

解题

方法一:动态规划

思路

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

思维过程

image-20230217052905521

动态规划
  • 状态定义:f[i][j]f[i][j] 表示所有只考虑ii 个数字,求和恰好为 jj所有选法数量

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

  • 初始状态:

    • 只考虑前 00 个数字,求和恰好为 00 时,空集是一种方案,故:f[0][0]=1f[0][0] = 1
    • 只考虑前 00 个数字,求和恰好为 1j1 \dots j 时,没有任何方案,故:f[0][1j]=0f[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;
}
0

评论区