Задача о рюкзаке методом динамического программирования

#include "pch.h"
#include <iostream>
#include <fstream>  
 
using namespace std;
 
int  wts[100], cost[100];
int *x = new int[100000];
int Sum_C = 0, Sum_W = 0, resW = 0, resC = 0;
int W;
int N = 1;
 
void print()
{
    int i;
 
    for (i = 1; i <= N; i++)
    {
        Sum_W = Sum_W + wts[x[i]];
        Sum_C = Sum_C + cost[x[i]];
 
        if (Sum_W <= W && Sum_C > resC) {
            resW = Sum_W;
            resC = Sum_C;
        }
    }
    Sum_C = 0;
    Sum_W = 0;
}
 
void Generate(int n, int k)
{
    int i, j, p;
    for (i = 1; i <= k; i++) x[i] = i;
    print();
    do
    {
        p = 0;
        for (i = k; i >= 1; i--)
            if (x[i] < n - k + i) { p = i; break; }
        if (p > 0)
        {
            x[p]++;
            for (i = p + 1; i <= k; i++) x[i] = x[i - 1] + 1;
            print();
        }
    } while (p > 0);
}
 
int main()
{
    int i = 1;
 
    cin >> W;
 
    while (!std::cin.eof())
    {
        cin >> wts[i];
        cin >> cost[i];
        i++;
    }
 
    while (N <= W)
    {
        Generate(W, N);
        N++;
    }
 
    cout << resW << " " << resC << endl;
 
    system("pause");
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int w,n(0),f,s,max_c(0),max_w(0);
 
int main()
{   
    cin >> w;
    //cin >> n;
    vector<int>weight,cost;
    while(cin >> f >> s){
        ++n;
        weight.push_back(f);
        cost.push_back(s);
    }
    //for(int i = 0;i<n;++i){       
    //  cin >> f >> s;
    //  weight.push_back(f);
    //  cost.push_back(s);
    //}
    int matrix[n+1][w+1];
    for(int i = 0;i<=w;++i)matrix[0][i] = 0;
    for(int i = 0;i<=n;++i)matrix[i][0] = 0;
    for(int i = 1;i<=n;++i){
        for(int j = 1;j<=w;++j)if(weight[i-1] <= j){
            matrix[i][j] = max(matrix[i-1][j],matrix[i-1][j-weight[i-1]] + cost[i-1]);
        } else matrix[i][j] = matrix[i-1][j];
    }
    vector<int>answer;
    for(int i = n;;){
        for(int j = w;;){
            if(!matrix[i][j])break;
            if(matrix[i][j] != matrix[i-1][j]){
                answer.push_back(i);
                max_c += cost[i-1];
                max_w += weight[i-1];
                j -= weight[i-1];
            } 
            --i;
        }
        break;
    }
    sort(answer.begin(),answer.end());
    cout << max_w << ' ' << max_c << '\n';
    for(int i = 0;i<answer.size();++i)cout << answer[i] << ' ';
    
    return 0;
}