Заполнить рюкзак предметами, чтобы стоимость рюкзака была максимальной

#include <iostream>
 
using namespace std;
 
int main()
{
    setlocale(LC_CTYPE, "rus");
    const int k = 9; // количество предметов
    const double W = 45; // вместимость рюкзака
    double w[k] = { 12,15,8,4,9,5,10,31,14 }; // масса
    double p[k] = { 11,10,6,16,10,7,8,10,8 }; // стоимость
    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");
}

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

#include<stdio.h>
#include<stdlib.h>
 
typedef struct items
{
    char name[20];
    unsigned int weight;
    float profit;
};
 
float max( float a, float b )
{
    return ((a>b)?a:b);
}
 
//Function to solve knapsack
float knapsack(unsigned int n, struct items object[], unsigned int capacity)
{
    float table[n+1][capacity+1];
    
    for(unsigned int i=0; i<=n; i++)
    {
        for(unsigned int j=0; j<=capacity; j++)     
        {       
            if( i==0 || j==0 )
                table[i][j] = 0.0;
            else if( object[i-1].weight <= j )
                table[i][j] = max( (object[i-1].profit + table[i-1][j-object[i-1].weight]), table[i-1][j] );
            else
                table[i][j] = table[i-1][j];
        }
    }
    
    //Printing table
    printf("Printing profit table\n");
    for(unsigned int i=0; i<=n; i++)
    {
        for(unsigned int j=0; j<=capacity; j++)     
            printf("%.1f\t",table[i][j]);
        printf("\n");
    }
    
    return table[n][capacity];
}
 
int main(void)
{
    //Input for Bag capacity
    unsigned int capacity;
    printf("Enter bag's capacity: ");
    scanf("%u",&capacity);
 
    //Input for number of items
    unsigned int n;
    printf("Enter total number of items: ");
    scanf("%d",&n);
 
    struct items item[n];
    
    //Input object details from user 
    printf("Enter Asked Details:\n");   
    for(unsigned int i=0; i<n; i++)
    {
        printf("==========Item No. %d ==========\n",i+1);
        printf("Item Name: ");
        scanf("%s",item[i].name);
        printf("Weight: ");
        scanf("%u",&item[i].weight);
        printf("Profit: ");
        scanf("%f",&item[i].profit);
    }
 
    //Solving knapsack problem
    float max_profit = knapsack(n, item, capacity);
    
    printf("Maximum Profit is %.2f.",max_profit);
 
    return 0;
}