Задача о рюкзаке

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <conio.h>
using namespace std;
 
const int n = 5;
const int k = 5; // количество предметов
int w[k] = { 10, 4, 3, 12, 5 }; // масса
int p[k] = { 12, 11, 1, 3, 36 }; // стоимость
const int W = 15; // вместимость рюкзака
int s = 5;
int A[k + 1][W + 1];
 
void out() {
    cout << "Все предметы рюкзака. Вес и стоимость: \n";
    for (int i = 0; i < n; i++) {
        cout << i + 1 << ") " << w[i] << " " << p[i] << "\n";
    }
}
 
void knapsack()
{
    for (int n = 0; n <= W; ++n)
        // Заполняем нулевую строчку
        A[0][n] = 0;
    for (int s = 1; s <= k; ++s)       // s - максимальный номер предмета, 
    {                       // который можно использовать
        for (int n = 0; n <= W; ++n)   // n - вместимости рюкзака
        {
            A[s][n] = A[s - 1][n];
            if (n >= w[s] && (A[s - 1][n - w[s]] + p[s] > A[s][n]))
                A[s][n] = A[s - 1][n - w[s]] + p[s];
        }
    }
}
 
void Print(int s, int n) {
    if (A[s][n] == 0) // максимальный рюкзак для параметров (s,n)
        return;        // имеет нулевую ценность, 
                       // поэтому ничего не выводим
    else if (A[s - 1][n] == A[s][n])
        Print(s - 1, n);  // можно составить рюкзак без предмета s
    else
    {
        Print(s - 1, n - w[s]); // Предмет s должен обязательно войти в рюкзак
        cout << s << endl;     
    }
}
 
int main()
{
    setlocale(LC_ALL, "rus");
    out();
    knapsack();
    cout << "Подходящие предметы: " << endl;
    Print(s, n);
    system("pause");
}

const int W = 20; // вместимость рюкзака

#include <iostream>
 
using namespace std;
 
int main()
{
    setlocale(LC_CTYPE, "rus");
    const int k = 5; // количество предметов
    const double W = 20; // вместимость рюкзака
    double w[k] = { 10, 4, 3, 12, 5 }; // масса
    double p[k] = { 12, 11, 1, 3, 36 }; // стоимость
    double mass[4][k]; //массив для расчетов
    double weight = 0; //суммарный вес
    double pay = 0; // суммарная стоимость
    for (int i = 0; i<k; i++)  //подсчет коэффициентов и заполнение строк массива
    {
        mass[0][i] = (p[i] / w[i]);
        mass[1][i] = w[i];
        mass[2][i] = p[i];
        mass[3][i] = i + 1;
        
    }
    for (int i = 0; i<k; i++) //распологаем в порядке убывания
    {
        for (int j = 0; j<k; j++)
        {
            double buffer;
            if (mass[0][i] > mass[0][j])
            {
                for (int z = 0; z < 4; z++)
                {
                    buffer = mass[z][i];
                    mass[z][i] = mass[z][j];
                    mass[z][j] = buffer;
                }
                
            }
        }
    }
    cout << "Подходящие предметы: ";
        for (int i = 0; i<k; i++)//выводим
        {
            weight += mass[1][i];
            if (weight <= W)
            {
                cout << mass[3][i] << " ";
                pay += mass[2][i];
            }
            else
            {
                weight -= mass[1][i];
            }
        }
    cout << endl << "Общий вес: " << weight << endl << "Сумма: " << pay << endl << endl;
    system("pause");
}

#include <iostream>
#include <algorithm>
#include <vector>
 
std::vector<int> weights{ 4, 1, 3 };// объём каждой вещи
std::vector<int> values{ 4000, 2500, 2000 }; // цена каждой вещи
 
// maxCapacity - объём рюкзака который надо заполнить
int countMax(int maxCapacity)
{
    //строим массив и закладываем место на ячейки пустышки 
    //выходящие из левого верхнего угла
    std::vector<std::vector<int>> arr( weights.size() + 1, std::vector<int>(maxCapacity + 1) );
 
    //проходим по всем вещам
    for (int i = 0; i <= weights.size(); i++)
    {
        //проходим по всем рюкзакам
        for (int j = 0; j <= maxCapacity; j++)
        {
            //попадаем в ячейку пустышку
            if (i == 0 || j == 0)
            {
                arr[i][j] = 0;
            }
            else
            {
                //если вес текущей вещи больше размера рюкзака
                //казалось бы откуда значение возьмется для первой вещи 
                //при таком условии. А оно возьмется из ряда пустышки
                if (weights[i - 1] > j)
                {
                    arr[i, j] = arr[i - 1, j];
                }
                else
                {
                    //здесь по формуле. Значение над текущей ячейкой
                    int prev = arr[i - 1][j];
                    //Значение по вертикали: ряд вверх
                    //и по горизонтали: вес рюкзака - вес текущей вещи
                    int byFormula = values[i - 1] + arr[i - 1][j - weights[i - 1]];
                    arr[i][j] = std::max(prev, byFormula);
                }
            }
        }
    }
 
    // возвращаем правую нижнюю ячейку
    return arr[weights.size()][maxCapacity];
}
 
int main()
{
    std::cout << countMax(4);
}

#include <iostream>
#include <algorithm>
#include <thread>
#include <vector>
#include <barrier>
 
std::vector<int> weights{ 4, 1, 3 };// объём каждой вещи
std::vector<int> values{ 4000, 2500, 2000 }; // цена каждой вещи
int const backpackCapacity = 7; // объём рюкзака
int const threadCount = 4; // число потоков
std::barrier br{ threadCount };
 
int main()
{
    // таблица вещей по верт. и рюкзаков по гориз.. В каждой ячейке суммарная ценность
    std::vector<std::vector<int>> table(weights.size() + 1, std::vector<int>(backpackCapacity + 1));
    
    std::vector<std::thread> vt;
    int const step = table[0].size() / threadCount;
    int const rem = table[0].size() % threadCount;
    int k = 0, lb = 0, ub = lb + step + rem;
    for (; k < threadCount; ++k)
    {
        vt.emplace_back([lb, ub, &table]()
            {
                //проходим по всем вещам таблицы
                for (int i = 0; i < table.size(); ++i)
                {
                    //проходим по всем рюкзакам таблицы
                    for (int j = lb; j < ub; ++j)
                    {
                        // нулевую строку и нулевой столбец таблицы обнуляем
                        if (i == 0 || j == 0)
                        {
                            table[i][j] = 0;
                        }
                        else
                        {
                            //если вес текущей вещи больше размера рюкзака
                            //казалось бы откуда значение возьмется для первой вещи 
                            //при таком условии. А оно возьмется из ряда пустышки
                            if (weights[i - 1] > j)
                            {
                                table[i][j] = table[i - 1][j];
                            }
                            else
                            {
                                //здесь по формуле. Значение над текущей ячейкой
                                int prev = table[i - 1][j];
                                // цена текущей вещи плюс цена оставшегося объёма рюкзака
                                int byFormula = values[i - 1] + table[i - 1][j - weights[i - 1]];
                                table[i][j] = std::max(prev, byFormula);
                            }
                        }
                    }
                    br.arrive_and_wait();
                }
            });
        lb = ub;
        ub = lb + step;
    }
 
    for (auto& t : vt)
    {
        t.join();
    }
    // возвращаем правую нижнюю ячейку
    std::cout << table[weights.size()][backpackCapacity];
}