#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include <windows.h>
#define N 6
#define MAX_ANS 1000
using namespace std;
struct node
{
int sum;
int loc;
};
int time=0;
int ans=0;
int nearest = 0;
int use[MAX_ANS][N+1];
void quick(vector<node>& a, int l, int r)
{
if(l < r)
{
int i=l, j=r, key=a[l].sum;
while(i<j)
{
while(i<j && a[j].sum>=key)
{
j
}
while(i<j && a[i].sum<=key)
{
i++;
}
swap(a[i], a[j]);
}
swap(a[i], a[l]);
quick(a, l, i-1);
quick(a, i+1, r);
}
}
int solve(vector<node> a, int target, int now, int sum, int r)
{
if(now<0 || now>N-1)
{
return 0;
}
if(use[ans][now] == 2) //这个节点还没有被访问过
{
int temp_sum = sum+a[now].sum;
if(now == N-1) //触底
{
if(temp_sum == target)
{
use[ans][now] = 1;
for(int i=0; i<N; i++)
{
use[ans+1][i] = use[ans][i];
}
ans++;
time++;
}
else if(temp_sum < target && (nearest > temp_sum || nearest == 0))
{
nearest = temp_sum;
use[ans][now] = 1;
for(int i=0; i<N; i++)
{
use[MAX_ANS-1][i] = use[ans][i];
}
}
else//直接转向右支触底
{
if(nearest > sum)
{
use[ans][now] = 0;
nearest = sum;
for(int i=0; i<N; i++)
{
use[MAX_ANS-1][i] = use[ans][i];
}
}
}
use[ans][now] = 2;
return solve(a, target, now-1, sum, r);
}
//没触底的正常处理流程
if(temp_sum == target) //等于就记录(time++)并且跳过这个节点
{
use[ans][now] = 1;
for(int i=0; i<N; i++)
{
use[ans+1][i] = use[ans][i];
}
ans++;
time++;
return solve(a, target, now, sum+a[now].sum, r-a[now].sum);
}
else if(temp_sum < target)
{
use[ans][now] = 1;
return solve(a, target, now+1, sum+a[now].sum, r-a[now].sum);
}
else
{
use[ans][now] = 2;
if(now < nearest)
{
nearest = now;
for(int i=0; i<N; i++)
{
use[MAX_ANS-1][i] = use[ans][i];
}
}
return solve(a, target, now-1, sum, r);
}
}
else//回溯
{
if(use[ans][now] == 1 && r+now>nearest) //该节点已经访问左支
{
use[ans][now] = 0;
return solve(a, target, now+1, sum-a[now].sum, r+a[now].sum);
}
else
{
use[ans][now] = 2;
return solve(a, target, now-1, sum, r);
}
}
return 0;
}
int main()
{
fstream input_stream;
input_stream.open("p08_w.txt", ios::in);
fstream target_stream;
target_stream.open("p08_c.txt", ios::in);
fstream ans_stream;
ans_stream.open("p02_s.txt", ios::in);
int target ;
vector<node> sum;
vector<string> std_ans;
node temp_flag;
string temp_string;
int temp_loc = 0;
while(!input_stream.eof())
{
input_stream>>temp_flag.sum;
temp_flag.loc = temp_loc++;
sum.push_back(temp_flag);
}
while(!target_stream.eof())
{
target_stream>>target;
}
while(!ans_stream.eof())
{
ans_stream>>temp_string;
std_ans.push_back(temp_string);
}
input_stream.close();
target_stream.close();
ans_stream.close();
for(int i=0; i<MAX_ANS; i++)
{
for(int k=0; k<N; k++)
{
use[i][k] = 2;
}
}
int len = sum.size();
quick(sum, 0, len-1);
int all = 0;
for(int i=0; i<len; i++)
{
all+=sum[i].sum;
}
LARGE_INTEGER start_time, end_time, tc;
QueryPerformanceFrequency(&tc);
QueryPerformanceCounter(&start_time);
solve(sum, target, 0, 0, all);
QueryPerformanceCounter(&end_time);
double duration_time = (double)(end_time.QuadPart-start_time.QuadPart) / tc.QuadPart;
cout<<duration_time<<endl;
for(int i=0; i<time; i++)
{
for(int k=0; k<N; k++)
{
if(use[i][k] == 2)
{
cout<<0<<" ";
}
else
{
cout<<use[i][k]<<" ";
}
}
cout<<endl;
}
cout<<endl;
int *print_ans = new int[len];
for(int i=0; i<time; i++)
{
for(int k=0; k<N; k++)
{
temp_loc = sum[k].loc;
int temp = use[i][k];
if(temp == 2)
{
print_ans[temp_loc] = 0;
}
else
{
print_ans[temp_loc] = temp;
}
}
for(int k=0; k<N; k++)
{
cout<<print_ans[k]<<" ";
}
cout<<endl;
}
if(time == 0)
{
for(int i=0; i<N; i++)
{
int temp = use[MAX_ANS-1][i];
if(temp == 2)
{
print_ans[sum[i].loc] = 0;
}
else
{
print_ans[sum[i].loc] = temp;
}
}
for(int i=0; i<N; i++)
{
cout<<print_ans[i]<<" ";
}
}
delete [] print_ans;
return 0;
}
|