#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>pii;
const int N = 1e3 + 10;
//1、暴力搜索
int kanpsackDFS(vector<int>& wgt, vector<int>&val, int i, int c) {
//已选完物品 或 背包无容量
if(i == 0 || c ==0) {
return 0;
}
//超过背包容量 则选择不放
if(wgt[i] > c) {
return kanpsackDFS(wgt, val, i-1, c);
}
// 计算放入和不放入的最大值
int no = kanpsackDFS(wgt, val, i-1, c);
int yes = kanpsackDFS(wgt, val, i-1, c - wgt[i]) + val[i];
return max(yes, no);
}
// 2、记忆化搜索
int knapsackDFSMem(vector<int>& wgt, vector<int>& val, vector<vector<int>>&mem, int i, int c){
//已选完所有物品 或 背包容量为0
if(i == 0 || c == 0) return 0;
//若有记录 直接返回
if(mem[i][c] != -1) return mem[i][c];
//超过背包容量 只能放入背包
if(wgt[i] > c) return knapsackDFSMem(wgt, val, mem, i-1, c);
//放入和不放入 选最大值
int no = knapsackDFSMem(wgt, val,mem,i-1,c);
int yes = knapsackDFSMem(wgt, val, mem, i-1, c - wgt[i]) + val[i];
mem[i][c] = max(no, yes);
return mem[i][c];
}
// 3、动态规划
int knapsackDP(vector<int>& wgt, vector<int>& val, int cap, int n){
vector<vector<int>>dp(n+1, vector<int>(cap+1, 0));
for(int i = 1; i <= n; i++){
for(int j = 0; j <= cap; j++){
if(wgt[i] > j) dp[i][j] = dp[i-1][j];
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-wgt[i]] + val[i]);
}
}
return dp[n][cap];
}
//4、空间优化 动态规划
int knapsackDPcomp(vector<int>&wgt, vector<int>&val, int cap, int n){
vector<int>dp(cap+1, 0);
for(int i = 1; i <= n; i++){
for(int j = cap; j >= 1; j--){
if(wgt[i] <= j){
dp[j] = max(dp[j], dp[j-wgt[i]] + val[i]);
}
}
}
return dp[cap];
}
void solve() {
int n, cap;
cin >> cap >>n;
vector<int> wgt(n+1, 0);
vector<int> val(n+1,0);
for(int i = 1; i <= n; i++) {
int w,v;
cin >> w >> v;
wgt[i] = w;
val[i] = v;
}
//1 、暴搜
// int res = kanpsackDFS(wgt, val, n, cap);
// cout << res << endl;
//2、记忆化搜索
// vector<vector<int>> mem(n+1, vector<int>(cap+1, 0));
// int res = knapsackDFSMem(wgt, val, mem, n, cap);
// cout << res << endl;
//3、动态规划
// cout << knapsackDP(wgt, val, cap, n) << endl;
//4、空间优化
cout << knapsackDPcomp(wgt, val, cap, n) << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
``