Сложная задача на С++

[Arigato]

int saw(double L, vector<double> l, vector<double> C, vector<int> &result){
    int max = 0;
    for(int i = 0; i < l.size(); i++){
        if(l[i] <= L){
            vector<int> r;
            int sum = C[i] + saw(L - l[i], l, C, r);
            if(sum > max){
                max = sum;
                result.assign(r.begin(), r.end()); 
                result.push_back(i);
            }
        }
    }
    return max;
}

int main()
{
    double L;
    int n;
    cout << "L n: ";
    cin >> L >> n;
    
    vector<double> l(n), C(n);
    for(int i = 0; i < n; i++){
        cout << "l" << (i + 1) << " C" << (i + 1) << ": ";
        cin >> l[i] >> C[i];
    }
    
    vector<int> result;
    int total = saw(L, l, C, result);
    cout << "Total: " << total << endl;
    for(int i = 0; i < result.size(); i++){
        cout << "l = " << l[result[i]] << ", C = " << C[result[i]] << endl;
    }
    
    return 0;
}

[сфинкс]

продолжая сообщение №10 ещё 5-минутный этюд
в отличие от многих программ формирует массивы сам
чему пора посвятить отдельную тему: массивы случайных на разных ЯП

а пока в qb64 qbasic назначаются длины и стоимости
и случайно перемешав номера вместо перебора
вводятся пока макс длину не превысят и считает суммы

и естественно недоделано зато считает всё само
без унижения пользователя вводом цифр в 21 веке

N = 5: L = 7: Dim L(N), C(N), j(N): Randomize Timer 'delim.bas
For i = 1 To N: L(i) = Int(Rnd * 3 + 1):
C(i) = 10 + Int(Rnd * 9): Print i, L(i), C(i): Next

5 For j = 1 To N: j(j) = Int(Rnd * N + 1): Next
For a = 1 To N - 1: For b = a + 1 To N
    If j(a) = j(b) Then GoTo 5
Next: Next: Print

s = 0: d = 0: For e = 1 To N
    d = d + L(j(e)): s = s + C(j(e))
    If d > L Then d = d - L(j(e)): s = s - C(j(e)): F = 1
    Print j(e), L(j(e)), d, C(j(e)), s
    If F = 1 Then GoTo 10
Next

опять получился индекс индекса
и немного исследуя: перемешивает без повтора на 50-й раз
поэтому все сразу додумывайте как переставлять неслучайно

пример работы N = 7: L = 5

 1             2             17 
 2             2             15 
 3             2             10 
 4             2             17 
 5             1             18 
 6             3             12 
 7             1             16 

 55 перестановок до комбинации неповторяющиейся 

 7             1             1             16            16 
 1             2             3             17            33 
 5             1             4             18            51 
 2             2             4             15            51

посчитан только 1 вариант и далее возможно перебрать все варианты
а здесь засим всё

автор темы указал с++? сможет переделать из бэйсик
и тему прочитают внезапно многие ... не только автор

ввод из файла недопустим в онлайн компиляторы
поэтому только синтез случайных или заданных не унижает

[Arigato]

Сообщение от сфинкс

в qb64 qbasic

Автор же указал язык C++, зачем здесь нужен Бейсик?

Сообщение от сфинкс

без унижения пользователя вводом цифр в 21 веке

Ввод из стандартного потока легко может быть перенаправлен из файла.

[digitalis]

Сообщение от Arigato

Автор же указал язык C++, зачем здесь нужен Бейсик?

"Бесик - это наше всё!" - сказал сами_знаете_кто
Полным перебором - тут много ума не надо. Но для больших чисел он очень затратен по времени выполнения. А вот решить "по-учёному"... Я приводил ссылку на метод динамического программирования, но если честно - сам его в данном применении не очень понял. Динамическим программированием поиск кратчайшего пути - приходилось решать, а тут что-то не въезжаю.

[сфинкс]

другой вариант: двоичный 2-ичный
вещь либо взяли либо не взяли
поэтому комбинаций 2^N и для N=5: 2^N=32 вместо N!=120

синтезируем произведения цены и длины то бишь интегралы
вновь только я пишу про интеграл

все варианты сравниваем с теми у кого длина менее заданной
и моя программа выше уже заполняет массивы
и остаётся перейти в 2-ичные массивы

через 5 минут:

N = 7: L = 5: Randomize Timer: a = 2*N ' ^ N 'dvoi4.bas
Dim L(N), C(N), j(N), q(a), q$(a), d(a)
Open "2.txt" For Output As #1
For i = 1 To N: L(i) = Int(Rnd * 3 + 1):
C(i) = 10 + Int(Rnd * 9): Print #1, i, L(i), C(i): Next

For h = 1 To a
    For k = 1 To N: j(k) = Int(Rnd + .5)
        q(h) = q(h) + L(k) * C(k) * j(k)
        q$(h) = q$(h) + Str$(j(k))
        d(h) = d(h) + L(k) * j(k)
    Next
    If d(h) <= L Then Print #1, d(h), q(h), q$(h)
Next
max = 0: m = 1: For i = 1 To a: If d(i) <= L Then If q(i) > max Then max = q(i): m = i   
Next
Print #1,: Print #1, d(m), q(m), q$(m): End

Результат:

 №          дл.ч.       стоим.ч.
 1             3             18 
 2             2             18 
 3             1             16 
 4             1             15 
 5             3             18 
 6             2             16 
 7             1             17 

Дл.полн.    Стоим.       Шифр интегральный 
 3             53            0 1 0 0 0 0 1
 5             85            0 1 0 0 0 1 1
 5             90            0 1 0 0 1 0 0
 4             64            0 0 0 1 0 1 1
 5             85            1 0 1 1 0 0 0
 3             49            0 0 0 0 0 1 1
 3             48            0 0 1 0 0 1 0

Максимум
5             90            0 1 0 0 1 0 0

Проверим результат 90 из 0100100 = 2*18+3*18 = 90 и длина L=5 из 5

оглавление: http://rosettacode.org/wiki/Knapsack_problem
long read: http://rosettacode.org/wiki/Knapsack_problem/0-1

Исходное условие цитата: "Из заготовки длиной L можно изготовить детали (ювелирные изделия) длины l1, l2,..., ln ценности С1, С2,…, Сn. Определить план распила заготовки, обеспечивающий максимальную суммарную ценность изготовленных деталей"

и даже если мечтают делить
в моей программе выдающей результаты изменится 1 символ с * на /
специально где не сообщаю

и мне больше интересны все перестановки 0 и 1
чтобы составить шифры и то в принципе понятно
осталось выразить короче даже если решается другая задача

[digitalis]

Сообщение от сфинкс

синтезируем произведения цены и длины

С виду - такое наукообразное, сразу и не скажешь, что фигня. Опять "произведение" ... Включить голову и спросить себя: что оптимальнее - отрезать кусок 1м ценой 100$ или 2м ценой 100$ ? Даже бабка с рынка с 4-мя классами ответит: конечно, первый вариант. Деньги те же, а в куске останется больше.
Может быть, на Бесике оно как-то по другому...
А вообще мне немного смешно: взяв наперевес курс информатики 8-го класса решать в лоб задачи, над которыми бились десятилетиями учёные мирового уровня, например
https://ru.wikipedia.org/wiki/Метод_ветвей_и_границ
Ну для 5..10 вариантов полный пребор ещё рулит, ну а как десятки-сотни - это уже не лаба-курсач, а диссертовина. Хотя конечно - современными Гигагерцами-Терабайтами можно в лоб решать задачи, которые раньше требовали напряжения ума.
---------------------------
Нам в Физтехе на АЯиЧМП ак. Моисеев Н.Н. рассказывал: когда в журнале было опубликовано сообщение об МВиГ - журнал был зачитан до дыр. И удивлялись: мы же это уже применяли не раз. Но вот сформулировать в виде метода додумалитсь только эти ребята.

[сфинкс]

допустим делим на ценность и получаем дробные
и заодно улучшил шифры добавив всегда начальные нули

N = 7: L = 5: a = 2 ^ (N + 1): Randomize Timer 'knap.bas
Dim L(N), C(N), j(N), q(a), q$(a), d(a)
Open "knap.txt" For Output As #1

For m = a - 1 To (a - 1) / 2 Step -1: g = m: Do ' sintez shifr
    q$(m) = LTrim$(Str$(g Mod 2)) + q$(m)
    g = g \ 2: Loop Until g = 0
    q$(m) = Mid$(q$(m), 2, Len(q$(m))) 'Print q$(m), a
Next

For i = 1 To N: L(i) = Int(Rnd * 3 + 1) ' lenght & cost
C(i) = 10 + Int(Rnd * 9): Print #1, i, L(i), C(i): Next ' origin

For h = a - 1 To (a - 1) / 2 Step -1
    For k = 1 To N: j(k) = Val(Mid$(q$(h), k, 1)) ' from shifr
        q(h) = q(h) + L(k) * j(k) / C(k) '  0 or 1
        d(h) = d(h) + L(k) * j(k)
    Next
    If d(h) <= L Then Print #1, d(h), q(h), q$(h)
Next
max = 0: m = 1: For i = 1 To a: If d(i) <= L Then If q(i) > max Then max = q(i): m = i
Next
Print #1,: Print #1, d(m), q(m), q$(m): End

Результат сокращён вручную:

№           Длина        Ценность
 1             1             18 
 2             1             18 
 3             2             15 
 4             1             15 
 5             1             16 
 6             2             15 
 7             1             11 
Длина      Сумма ценности     Шифр
 5             .3111111     1111000
 5             .3069445     1110100
 5             .3353536     1110001
 4             .2444445     1110000
 5             .3311869     1101101
 4             .2402778     1101100
 5             .3534091     0011101
 5             .3333334     0011010
 4             .2909091     0011001
 5             .3575758     0010011
 4             .2666667     0010010
 3             .2242424     0010001
 2             .1333333     0010000
 5             .3534091     0001111
 4             .2625        0001110
 3             .2200758     0001101
 2             .1291667     0001100
 4             .2909091     0001011
 3             .2           0001010
 3             .1958333     0000110
 2             .1534091     0000101
 2             .1333333     0000010

 5             .3575758     0010011

Дробный результат проверить люди неспособны
поэтому лучше умножать на ценность то бишь интегрировать
и заодно программа короткая и понятная даже школьникам

данный мой оригинальный алгоритм не жадный
плюс оглавление про рюкзак на разных ЯП
http://rosettacode.org/wiki/Knapsack_problem

[macomics]

Задумайтесь вот о чем. Решать задачу с помощью жадного алгоритма можно, но он не эффективен, если в результате его работы остался остаток, хотя его разбиение является максимально эффективным для разбитого отрезка. Тогда у нас остается отрезок длинной r и искать динамическим программированием надо не все разбиение, а только для конца отрезка меньшей длины. За исходное разбиение можно принять то, что дал жадный алгоритм, прибавляя к нему по кусочку и выполняя динамическим программированием разбиение маленького кусочка с меньшей длиной чем (n - i) * max(l / C) (i = НОД(max(l / C), min(l /C))).
Таким образом перебор и расход памяти в динамическом методе будет минимальным, а при полном разбиении жадным алгоритмом и вовсе не понадобится.