Поиск наименьшей суммы длин между элементами

Обозначим L(i,k) - оптимальное множество ребер, задевающих вершины с i-й по k-ю включительно, использую ребра с номерами от i до k-1 влючительно. Решение по поиску такого множества, выразим через решение задачи для более коротких отрезков: L(i,k) = min{ L(i,k-1)+a[k-1] , L(i, k-2)+a[k-1] } где минимальное из двух множеств, считается по сумме весов элементов. Имея решение для линейного отрезка, можно выразить решение для полного цикла: L_all = min{ L(1,n), L(2,n-1) + a[n] }.

Решение:

#include <iostream>
#include <functional>
#include <type_traits>
#include <vector>

using a_t = std::vector<double>;
using L_t = std::vector<size_t>;

// добавляем элемент в конец вектора.
L_t push_back( L_t L, size_t i )
{
    L.push_back(i);
    return L;
}

// длинна множества ребер L, при весах a.
int L_len( const a_t& a, const L_t& L )
{
    double summ = 0;
    for(auto i : L)
        summ += a[i];
    return summ;
}

L_t L_min( const a_t& a, L_t L1 , L_t L2 )
{
    return (L_len(a,L1)<L_len(a,L2)) ? L1 : L2;
}

L_t L( const a_t& a, size_t i, size_t k )
{
    std::vector<L_t> L_ij(k+1);
    L_ij[i+1] = {i};
    L_ij[i+2] = {i, i+1};
    for( size_t j=i+3; j<=k; ++j )
        L_ij[j] = L_min( a,
                         push_back( L_ij[j-1] , j-1),
                         push_back( L_ij[j-2] , j-1) );
    return L_ij[k];
}

L_t solve( const a_t& a )
{
    size_t n = a.size();
    return L_min( a,
                  L(a, 0, n-1 ),
                  push_back( L(a, 1, n-2 ) , n-1 )
                  );
}

int main()
{
    for(auto i : solve({1,2,5,1,1,6}) )
        std::cout<<i<<std::endl;
}

Избавление от массива L_ij (достаточно хранить только два предыдущих элемента), и оптимизацию (можно соптимизировать до O(n) вместо O(n^2)) оставляем автору вопроса.

В итоге я все-таки нашел способ решения. Для упрощения сделал как задачу о зверьках, но смысл одинаковый этих двух задач.

/**
* Задача:
* Дано n зверей, так-же дан массив a, где число - количество денег для кормежки двух зверьков.
* n = 3
* 1 2 3 -> 3
* a1 = 1 (расстояние между точкой 1 и 2)
* a2 = 2 (расстояние между точкой 2 и 3)
* a3 = 3 (расстояние между точкой 3 и 1)
* 
* 3 - ответ.
*/

#include <iostream>     // std::cin, std::cout
#include <vector>       // std::vector
#include <algorithm>    // std::find
#include <string>       // std::string

struct itemT;           // Храним данные о зверьках.
struct itemL;           // Храним данные о стоимости кормешки рядом двух зверьков.

using namespace std;    // in std namespace

/**
* Структура для хранения зверьков.
* 
* Включает в себя имя, стоимость кормешки с предыдущим 
* и стоимость кормешки с зверьком впереди.
*/
struct itemT
{
    string name;
    itemL* prev;
    itemL* next;
};

/**
* Структура для хранения стоимости кормешки двух рядом стоящих зверьков.
*
* Включает в себя имя ребра, стоимость кормешки,
* указатели на первого зверька и следущего зверька.
*/
struct itemL
{
    string name;
    int cost;
    itemT* first;      
    itemT* second;
};

/**
* Структура для хранения резульататов поиска оптимального решения 
* с сохранением порядка кормешки.
*/
struct varData
{
    vector<string> seq;
    int cost;

    varData(vector<string> seqData, int costData)
    {
        seq = seqData;
        cost = costData;
    };
};


/**
* Класс для удобной работы с массивом зверушек.
*/
class LoopedReadOnlyArrayClass
{
    itemT* arrayItem_T;
    int lengthArrayValue;

public:
    /**
    * Конструктор, принимающий массив обьектов и размер массива.
    */
    LoopedReadOnlyArrayClass(itemT* items, int n) 
    {
        arrayItem_T = new itemT[n];
        for (int i = 0; i < n; i++)
            arrayItem_T[i] = items[i];
        lengthArrayValue = n;
    }

    /**
    * Метод для получения обьекта по данному индексу.
    */
    itemT get(int i) 
    {
        return arrayItem_T[i % lengthArrayValue];
    }

    /**
    * Метод для получения размера массива.
    */
    int length() 
    {
        return lengthArrayValue;
    }
};


int main()
{

    setlocale(LC_ALL, "ru");

    /**
    * Получаем данные о количестве зверушек.
    */
    int n;
    cin >> n;

    /**
    * Получаем данные о стоимости кормешки.
    */
    int* a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    /**
    * Трансформируем в удобную форму хранения данных.
    */
    itemT* arrayAnimal = new itemT[n];
    itemL* arrayAnimalCostLength = new itemL[n];

    cout << "Отображаю стоимость кормешки..." << endl;

    for (int i = 0; i < n; i++)
    {
        if (i == (n - 1))
        {
            arrayAnimalCostLength[i].name = "l" + std::to_string(i + 1);
            arrayAnimalCostLength[i].cost = a[i];
            arrayAnimalCostLength[i].first = &arrayAnimal[i];
            arrayAnimalCostLength[i].second = &arrayAnimal[0];

            cout << "CostLenght: " << "[ name:" << arrayAnimalCostLength[i].name << " cost:" << arrayAnimalCostLength[i].cost << " first: " << i+1 << " sec: " << 1 << " ]" << endl;
        }
        else
        {
            arrayAnimalCostLength[i].name = "l" + to_string(i + 1);
            arrayAnimalCostLength[i].cost = a[i];
            arrayAnimalCostLength[i].first = &arrayAnimal[i];
            arrayAnimalCostLength[i].second = &arrayAnimal[i + 1];

            cout << "CostLenght: " << "[ name:" << arrayAnimalCostLength[i].name << " cost:" << arrayAnimalCostLength[i].cost << " first: " << i+1 << " sec: " << i + 2 << " ]" << endl;
        }

    }


    cout << "\n\nОтображаю животных..." << endl;

    for (int i = 0; i < n; i++)
    {
        if (i == (n - 1))
        {
            arrayAnimal[i].name = to_string(i+1);
            arrayAnimal[i].next = &arrayAnimalCostLength[i];
            arrayAnimal[i].prev = &arrayAnimalCostLength[0];

            cout << "Animal: " << "[ name:" << arrayAnimal[i].name << " next:" << i + 1 << " prev:" << 1 << " ]" << endl;
        }
        else
        {
            arrayAnimal[i].name = to_string(i+1);
            arrayAnimal[i].next = &arrayAnimalCostLength[i];
            arrayAnimal[i].prev = &arrayAnimalCostLength[i + 1];

            cout << "Animal: "  << "[ name:" << arrayAnimal[i].name << " next:" << i+1 << " prev:" << i + 2 << " ]" << endl;
        }
    }
    /*
    * Трансформируем данные и используем удобный обьект,
    * для работы с данным массивом зверушек и их стоимости кормешки.
    */
    LoopedReadOnlyArrayClass* arrAdvanced = new LoopedReadOnlyArrayClass(arrayAnimal, n);

    /**
    * Вектор для хранения данных о результатах поиска оптимального процесса кормешки.
    */
    vector<varData> variants = {};

    /**
    * Проверяем варианты...
    */
    for (int i = 0; i < arrAdvanced->length(); i++) 
    {
        vector<string> seq = {};
        vector<string> feeded = {};
        int cost = 0;

        for (int j = 0; j < arrAdvanced->length(); j++) 
        {
            itemT element = arrAdvanced->get(i + j);

            if ((find(feeded.begin(), feeded.end(), element.name) != feeded.end())) 
            {
                continue;
            }

            cost += element.next->cost;

            feeded.push_back(element.next->first->name);
            feeded.push_back(element.next->second->name);

            seq.push_back(element.next->name);
        }
        variants.push_back({ seq, cost }); // Заносим данные в вектор.

        //Если нужно вывести все варианты, раскоментируйте этот код.
        //for (auto i : seq)
        //    cout << i << ' ';
        //cout << " Cost:" << cost << endl;
    }

    /**
    * Ищем среди вариантов данных самый лучший вариант.
    */
    int minCost = INT_MAX;
    vector<string> varDataItem;
    for (int i = 0; i < variants.size(); i++)
    {
        if (variants[i].cost < minCost)
        {
            minCost = variants[i].cost;
            varDataItem = variants[i].seq;
        }
    }

    cout << "\n\nРезультат:" << endl;

    for (auto i : varDataItem)
        cout << i << ' ';
    cout << " Стоимость: " << minCost << endl;

    return 0;
}

Так-же выкладываю код на JS:

let a = { name: "a", prev: null, next: null };
let b = { name: "b", prev: null, next: null };
let c = { name: "c", prev: null, next: null };
let d = { name: "d", prev: null, next: null };
let e = { name: "e", prev: null, next: null };
let f = { name: "f", prev: null, next: null };

let l1 = { name: "l1", cost: 1, first: a, second: b };
let l2 = { name: "l2", cost: 2, first: b, second: c };
let l3 = { name: "l3", cost: 3, first: c, second: d };
let l4 = { name: "l4", cost: 4, first: d, second: e };
let l5 = { name: "l5", cost: 5, first: e, second: f };
let l6 = { name: "l6", cost: 6, first: f, second: a };

/////

a.prev = l6;
a.next = l1;

b.prev = l1;
b.next = l2;

c.prev = l2;
c.next = l3;

d.prev = l3;
d.next = l4;

e.prev = l4;
e.next = l5;

f.prev = l5;
f.next = l6;

/////

class LoopedReadOnlyArray {
    #array;

    constructor(array) {
        this.#array = array;
    }

    get(i) {
        return this.#array[i % this.#array.length];
    }

    length() {
        return this.#array.length;
    }
}

/////

let arr = new LoopedReadOnlyArray([ a, b, c, d, e, f ]);

/////

const variants = [];

for (let i = 0; i < arr.length(); i++) {
    let seq = [];
    let feeded = [];
    let cost = 0;

    for (let j = 0; j < arr.length(); j++) {
        const element = arr.get([i + j]);

        if (feeded.includes(element.name)) {
            continue;
        }

        cost += element.next.cost;

        feeded.push(element.next.first.name);
        feeded.push(element.next.second.name);

        seq.push(element.next.name);
    }

    variants.push({ seq, cost });
}

console.log(variants);

Лог:

[
  { seq: [ 'l1', 'l3', 'l5' ], cost: 9 },
  { seq: [ 'l2', 'l4', 'l6' ], cost: 12 },
  { seq: [ 'l3', 'l5', 'l1' ], cost: 9 },
  { seq: [ 'l4', 'l6', 'l2' ], cost: 12 },
  { seq: [ 'l5', 'l1', 'l3' ], cost: 9 },
  { seq: [ 'l6', 'l2', 'l4' ], cost: 12 }
]