#include<iostream> #include<vector> #include<ctime> #include<deque> #include<list> #include<algorithm> #include<queue> #include<functional>//greater使用 using namespace std; //打印函数 void print(vector<int> a) { for (int i = 0; i < a.size(); i++) { cout << a[i] << " "; } cout << endl; } //递归版本 bool fun(vector<int>& arr,int i,int s) { if (s == 0) return true; else if (i == 0) return arr[i] == s; else if (arr[i] > s) { return fun(arr, i - 1, s); } else { bool A = fun(arr, i - 1, s - arr[i]); bool B = fun(arr, i - 1,s); return A | B; } } //递归从后往前，DP从前往后 int main() { vector<int> arr{ 3,34,4,12,5,2}; //递归版本 int s = 9; bool ans = fun(arr, size(arr)-1, s); cout << ans << endl; //非递归版本 //原始数组一共有六个元素 vector<vector <bool> > subset(size(arr), vector<bool>(10, 0)); //第一列是0 for (int i = 0; i < subset.size(); i++) { subset[i][0] = true; } for (int i = 0; i < subset[0].size(); i++) { subset[0][i] = false; } subset[0][arr[0]] = true; for (int i = 1; i < subset.size(); i++) { for (int j = 1; j < subset[0].size(); j++) { if (arr[i] > j) { subset[i][j] = subset[i - 1][j]; } else { bool A = subset[i - 1][j - arr[i]]; bool B = subset[i - 1][j]; subset[i][j] = A|B; } } } cout << subset[subset.size() - 1][subset[0].size() - 1] << endl; system("pause"); }
