回溯第一题 #include <iostream> #include<string> #include<vector> #include<stack> #include<vector> using namespace std; int max = 0; void dfs(vector<int> number, vector<int> capacity, int n, int m, int index1, int index2, int corrent); int main(int argc, char* argv[]) { int n; int t; int m; while (cin >> n) { cin >> t; cin >> m; vector<int> number(n); for (int i = 0; i < n; i++) { cin >> number[i]; } vector<int> capacity(m); for (int i = 0; i < m; i++) { capacity[i] = t; } int index1 = 0; int index2 = 0; int corrent = 0; dfs(number,capacity, n, m,0,0,0 ); cout << max << endl; } return 0; } void dfs(vector<int> number, vector<int> capacity, int n, int m, int index1,int index2,int corrent) { if (index1 == n||index2==m) { if (corrent > max) max = corrent; return; } if (capacity[index2] >= number[index1]) { capacity[index2] = capacity[index2] - number[index1]; index1++; corrent++; dfs(number, capacity, n, m, index1, index2, corrent); index1--; capacity[index2] = capacity[index2] +number[index1]; corrent--; } else if (capacity[index2] <= number[index1] && index2 + 1 < m&&capacity[index2 + 1] > number[index1]) { index2++; capacity[index2] = capacity[index2] - number[index1]; index1++; corrent++; dfs(number, capacity, n, m, index1, index2, corrent); index1--; corrent--; capacity[index2] = capacity[index2] + number[index1]; index2--; } index1++; dfs(number, capacity, n, m, index1, index2, corrent); index1--; }