回溯第一题

#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--;

}