9

#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>

using namespace std;
////////////////////////////
const int N = 7;
int test_size[N]={0};
int sum = 0;
int record = 0;
int price1 = 0;
int index = 0;
int max_s = 30;


void forw(float v[] , float c[]){
    for(int i = index; i < N; i++){
        if(v[i] + sum <= max_s){
            test_size[i] = 1;
            sum+=v[i];
            //price1 += c[i];
        }
        else test_size[i] = 0;
    }
    //if(record < price1)
        //record = price1;
}

void check(float v[] , float c[]){
    sum = 0;
    for(int i = 0; i < N; i++){
        sum+=v[i]*test_size[i];
        price1+=c[i]*test_size[i];
    }
    if(sum > max_s || price1 < record)
        return;
    else record = price1;
    price1 = 0;
}

int backing(float v[] , float c[]){
    if(test_size[N-1]){
        test_size[N-1] = 0;
        sum-=v[N-1];
    }
    for(int i = N-2; i >=0; --i){
        if(test_size[i]){
            test_size[i] = 0;
            sum-=v[i];
            index = i + 1;
            return 1;
        }
        return 0;
    }
}

void outF(float a[]) {
    printf("\n{ ");
for(int i=0; i<N; ++i) {
    if(i<N-1)
        printf("%2.2f, ", a[i]);
    else
        printf("%2.2f }\n", a[i]);
}
}

int main()
{
    //cout << "INPUT COUNT THINGS" << endl;
    //cin >> N; /// вводим число вещей
    //cout << "INPUT SIZE OF BACKPACK" << endl;
    //cin >> max_s;
    float v[N] = {7 , 10 , 15 , 25 , 30 , 20 , 15}; /// массив веса вещи
    float c[N] = {49 , 60 , 120 , 50 , 90 , 40 , 150};/// массив стоимости вещи
    float u[N]; /// массив удельной стоимости 1 вещи (индексы сохраняются по порядку)
    for(int i=0; i<N; ++i) {
        u[i] = (float)(c[i]/v[i]);
   }
   float arr[N] = {0};
    for(int i=0; i<N; i++)
        for(int j=1; j<N-1; j++)
            if(u[j] > u[i]) {
                int t = u[j];
                u[j] = u[i];
                u[i] = t;

                 t = c[j];
                c[j] = c[i];
                c[i] = t;

                 t = v[j];
                v[j] = v[i];
                v[i] = t;
            }

    cout << "things:";
    outF(v);
    cout << "prices:";
    outF(c);
    cout << "unit cost:";
    outF(u);

    do {
        forw(v , c);
        check(v , c);
    } while(backing(v , c));
    printf("\nRESULT OF ALGORITHM 3rd: %d", record);
    return 0;
}