一维数组解决背包问题

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  7. using namespace std;
  9. int main()
  10. {
  11.     int N, M;
  12.     scanf_s("%d%d", &N, &M);
  13.     int need[503], value[503];
  14.     for (int i = 0; i < N; i++)
  15.     {
  16.         scanf_s("%d%d", &need[i], &value[i]);
  17.     }
  18.     int dp[100010];
  19.     memset(dp, 0, sizeof(dp));
  20.     /**
  21.     f(j)=max(f(j),f(j-need(j));
  22.     */
  23.     for (int i = 0; i < N; i++)
  24.         for (int j = M; j >= need[i]; j--)
  25.             dp[j] = max(dp[j], dp[j - need[i]] + value[i]);
  26.     printf_s("%d\n", dp[M]);
  28.     return 0;
  29. }

完全背包问题

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. const int maxn = 1e5 + 10;
  7. using namespace std;
  9. int main()
  10. {
  11.     int dp[maxn], w[101], v[101];
  12.     int n, m;
  13.     cin >> n >> m;
  14.     for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
  15.     memset(dp, 0, sizeof(dp));
  16.     for (int i = 0; i < n; i++)
  17.         for (int j = w[i]; j <= m; j++)
  18.             dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  19.     cout << dp[m];
  20.     return 0;
  21. }