This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
#include <bits/stdc++.h>
using namespace std;
int main() {
//输入+输出重定向
freopen("../1297.txt", "r", stdin);
//背包的称重上限
int M, N;
cin >> M >> N;
vector<int> w = {N + 1, 0}; //重量
vector<int> v = {N + 1, 0}; //价值
vector<int> dp(M + 1, 0); //DP表，初始值0
//读取入数据
for (int i = 1; i <= N; i++) {
cin >> w[i] >> v[i];
}
//使用一维数组的优化方法
for (int i = 1; i <= N; i++) //5种商品，依次设置为可以选择
for (int j = w[i]; j <= M; j++)//依次检查是不是重量可以放下这个物品（注意从小到大，表示是完全背包，从大到小是01背包）
dp[j] = max(dp[j], dp[j - w[i]] + v[i]); //如果将这个物品放入，是不是会产生更优化的解
cout << dp[M] << endl;
//关闭文件
fclose(stdin);
return 0;
