本文主要是介绍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背包)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!