AcWing 278.数字组合

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

首先就是可以给出DFS的思路，也就是指数型递归的操作：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define int long long
#define MAX 100
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII=pair<int, int>;
int n, m;
int counts;
int w[MAX];
int st[MAX];
void dfs(int u, int sum) {if (sum > m)return;if (u > n) {if (sum == m)counts++;return;}if (sum + w[u] > m)dfs(u + 1, sum);else{st[u] = 1;dfs(u + 1, sum + w[u]);st[0];st[u] = 2;dfs(u + 1, sum);st[u] = 0;}}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> w[i];}dfs(1, 0);cout << counts;return 0;
}

当然，时间是超时的。

接下来就是对于此的DP优化。

对于这个问题也就是说是一个01背包问题的方案数是求解，此时我们的f数组的含义也就变了，也就是从最大利用价值变成了能够得出目标数的方案数这个含义。

数组由于过了万，所以不能用二维数组进行求解，只能对于二维数组优化空间为一维数组。

上代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<set>
#define int long long
#define MAX 10005
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII=pair<int, int>;
int n, m;
int counts;
int w[MAX];
int f[MAX];
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> w[i];}f[0] = 1;for (int i = 1; i <= n; i++) {for (int j = m; j >= 0; j--) {if (j < w[i])f[j] = f[j];elsef[j] = f[j] + f[j - w[i]];}}cout << f[m];return 0;
}

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

---