View Code of Problem 4045

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct S{
    int weight;
    int value;
}s[1001];

bool cmp(S a,S b){
    if(a.weight == b.weight)
        return a.value > b.value;
    else
        return a.weight < b.weight;
}

int main(void)
{
    int max_weight, n;
    scanf("%d %d",&max_weight,&n);
    for (int i = 0; i < n;i++){
        scanf("%d %d", &s[i].weight, &s[i].value);
    }
    int dp[max_weight + 1] = {0};
    for (int i = 0; i < max_weight+1;i++){
        for (int j = max_weight; j >= s[i].weight;j--){
            dp[j] = max(dp[j], dp[j - s[i].weight] + s[i].value);
        }
    }
    cout << dp[max_weight] << endl;
}