给定 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

题目分析

01背包

代码实现

#include <iostream>
using namespace std;
const int N = 1e4 + 10;

int n, V, v, dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> V;
    dp[0] = 1;
    while(n--) {
        cin >> v;
        for (int i = V; i >= v; --i) dp[i] += dp[i - v];
    }
    cout << dp[V];
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status