完全背包

 1 #include 
 2 #define int long long
 3 using namespace std;
 4 const int mx = 1e7 + 9;
 5 int n, m, dp[mx], w[mx], v[mx];
 6 signed main() {
 7     cin >> m >> n;
 8     for (int i = 0; i < n; i++) {
 9         cin >> w[i] >> v[i];
10     }
11     for (int i = 0; i < n; i++) {
12         for (int j = w[i]; j <= m; j++) {
13             dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
14         }
15     }
16     cout << dp[m];
17     return 0;
18 }

//刚好装满
#include 
#include 
using namespace std;
const int mx = 1e5 + 7;
int n, m, w, v, dp[mx];
int main(){
 
    cin >> n >> m;
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= n; i++){
        cin >> w >> v;
        for (int j = w; j <= m; j++){
            if (dp[j - w] == -1) continue;
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    if (dp[m] == -1) printf("NO\n");
    else printf("%d\n", dp[m]);

    return 0;
}