停车问题 | 回溯法

描述

在丹泽大街上，汽车可以停在街道的两边。爱德蒙先生住在一号，他正在组织一个私人的聚会，客人将乘坐N辆车到达。第i辆车占用的长度为λi，单位为米，如下所示为N=15的情况：

为了避免打扰邻居们，爱德蒙先生想把街道两边的停车位安排好，这样他朋友的车占用的街道长度应该是最小的，其中他家对面的那一边街道的长度不超过15米。

利用分支限界法求解该问题.

输入

第一行输入t，表示测试用例的个数，每个测试用例第一行输入整数N，表示有N辆车，第二行输入N个正实数，表示每辆车所占停车位的长度。

输出

对于每一个测试用例，输出一个正实数，表示停车所占用的街道的长度（取街道两边停车占用的最长值）。末行有换行，1位小数

样例解析

只有1个测试用例，其中第1，2，5，7号车停一边，3，4，6号车停一边，则

4+4.5+2.4+3.7=14.6

5+4.1+5.2=14.3

所以停车占用街道的长度为14.6

输入样例 1 

1
7
4 4.5 5 4.1 2.4 5.2 3.7

输出样例 1

14.6

题解：

        一辆车要不停左边，要不停右边，直接回溯求解。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long int ll;

int t=0,n=0,i,j;
double length[1001]={0},sum=0,s1=0,s2=0,mins=100000;

void solution(int i){
    if(s2>15){
        return;
    }
    else if(i==n){
        if(max(s1,s2)<mins){
            mins=max(s1,s2);
        }
        return;
    }

    s1+=length[i];
    solution(i+1);
    s1-=length[i];
    s2+=length[i];
    solution(i+1);
    s2-=length[i];
}

main()
{
    cin >> t;
    while(t>0){
        cin >> n;
        for(i=0;i<n;i++){
            cin >> length[i];
        }
        solution(0);
        cout << mins << "\n";
        mins=100000;s1=0;s2=0;
        t--;
    }
}