A70751. 数字的组合
编程题
基础
知识点
题目描述
给定 N 个正整数 A_1,A_2,…,A_N，从中选出若干个数，使它们的和为 M ，求有多少种选择方案。
注意：选择不同位置的，但值相同的数，认为是不同的方案。
比如：有 3 个数 1 1 1，要组合出 2，那么有 3 个方案，分别是选第 1、2 个数，选第 1、3 个数，选第 2、3 个数。
输入格式
第一行包含两个整数 N 和 M 。
第二行包含 N 个整数，表示 A_1,A_2,…,A_N 。
数据范围
1≤N≤100,1≤M≤10000,1≤A_i≤1000。
输出格式
包含一个整数，表示可选方案数（本题的计算结果一定在int范围内）。
输入输出样例
输入 #1
4 4 1 1 2 2
输出 #1
3
说明/提示
## 思路
背包 DP：状态为容量（及物品），转移为选或不选当前物品。
## 步骤
1. 读入容量与物品体积/价值。
2. 按 01 或完全背包的循环顺序填 dp。
3. 输出最大价值或方案数。
背包 DP：状态为容量（及物品），转移为选或不选当前物品。
## 步骤
1. 读入容量与物品体积/价值。
2. 按 01 或完全背包的循环顺序填 dp。
3. 输出最大价值或方案数。