louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=30334

題目大意:  問在有限的金錢下，最大的獲利 錢乘重要度最大。

思路:  背包問題，每個錢都可以放或不放。01背包。跟前面幾題差不多。

代碼:  

#include <bits/stdc++.h>
#define N 3005
#define M 30
using namespace std;

int money[M], p[M], dp[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        cin >> money[i] >> p[i];
    }
    for(int i = 0; i < m; ++i){
        for(int j = n; j >= money[i]; --j){
            dp[j] = max(dp[j], dp[j-money[i]] + money[i]*p[i]);
        }
    }
    cout << dp[n] << endl;
    return 0;
}