01背包不可达状态 二维的

include <bits/stdc++.h>

using namespace std;

int j[1005];
int f[1005];
int dp[1005][1005];

int main() {
int m, n;
while (cin >> m >> n) {
if (m == -1 && n == -1) break;

    memset(dp,-1,sizeof(dp));for (int i = 1; i <= n; i++) {cin >> j[i] >> f[i];}dp[0][0]=0;//其余的被认为是不可达状态 for(int i=1;i<=n;i++){for(int jj=0;jj<=m;jj++){if(jj<f[i]) {dp[i][jj]=dp[i-1][jj];//没得选 }else{if(dp[i-1][jj-f[i]]!=-1)dp[i][jj]=max(dp[i-1][jj],dp[i-1][jj-f[i]]+j[i]);//没选  选了  必须可达才可以更新的 }}}cout<<dp[n][m]<<endl;
}
return 0;

}