信息学奥赛一本通T1268-完全背包问题(C++)

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

int w[31];

int c[31];

int dp[201] = {0};

int main()

{

    int m, n;

    cin >> m >> n;

    for (int i = 0; i < n; i++) {

        cin >> w[i] >> c[i];

    }

    for (int i = 1; i <= m; i++) {

        for (int j = 0; j < n; j++) {

            if (i >= w[j]) {

                dp[i] = max(dp[i], dp[i - w[j]] + c[j]);

            }

        }

    }

    cout << "max=" << dp[m];

    return 0;

}