[基础dp]Aizu – ALDS1_5_A-Exhaustive Search

发布于 2019-07-24  1608 次阅读


https://vjudge.net/problem/Aizu-ALDS1_5_A

蒟蒻开始接触dp了 第一道dp好像很简单

题意:给定一个数组 问选任意个元素是否能够凑出所给的数字 如果可以 输出yes 否则输出no


思路:就是对于每个元素 有选或者不选两种选择 直到选的个数超过了最大个数(失败)或者所选元素之和刚刚好就是所求的数字(成功)

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<ctime>
#include<map>
#include<stack>
#include<set>
#include<cstring>
#include<sstream>
using namespace std;
typedef long long ll;
int n;
int arr[25];

int solve(int i, int m) {
	if (m == 0) {//剩余量为0
		return 1;//解决问题
	}
	else if (i >= n) {//用的元素个数超过了n
		return 0;
	}
	return solve(i + 1, m) + solve(i + 1, m - arr[i]);//递归 选用当前元素或者不选用当前元素
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int m, t;
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> t;
		if (solve(0, t)) {
			cout << "yes" << endl;
		}
		else {
			cout << "no" << endl;
		}
	}
	return 0;
}

愿风指引你的道路,愿你的刀刃永远锋利。