278.数字组合（01背包）

本文主要是介绍278.数字组合（01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

输入格式
第一行包含两个整数N和M。

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

输出格式
包含一个整数，表示M。

数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000
输入样例：
4 4
1 1 2 2
输出样例：
3

思路： 只能选一次，所以子状态必须是没用选过的，所以得逆序找没有更新过的子状态。

#include <cstdio>
#include <cstring>using namespace std;const int maxn = 10000 + 7;
int dp[maxn],a[maxn];//The value when the sum it i.
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++){scanf("%d",&a[i]);}dp[0] = 1;for(int i = 1;i <= n;i++){for(int j = m;j >= a[i];j--){dp[j] += dp[j - a[i]];}}printf("%d\n",dp[m]);return 0;
}

这篇关于278.数字组合（01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---