本文迁移自老博客，原始链接为 https://seven.blog.ustc.edu.cn/usacoscore-inflation/
完全背包。动态规划的方程是dp[w] = Max( dp[w-o[i].wei]+o[i].val) , dp[w])，方程的形式和0-1背包是相同的，但是容量的循环的顺序不同。
#include<iostream>
#include<algorithm>
#include<fstream>
#include<string.h>
using namespace std;
ofstream fout ("inflate.out");
ifstream fin ("inflate.in");
const int nMax = 10001;
const int mMax = 10001;
struct point
{
int val;
int wei;
}o[mMax];
int main()
{
int n,m,i,w,dp[nMax];
fin>>m>>n;
for(i = 1; i <= n; i++)
fin>>o[i].val>>o[i].wei;
memset(dp,0,sizeof(dp));
for(i = 1; i <= n; i++)
for(w =o[i].wei; w<=m; w++)
if(dp[w] < dp[w-o[i].wei] + o[i].val)
dp[w] = dp[w-o[i].wei] + o[i].val;
fout<<dp[m]<<endl;
return 0;
}
