louisfghbvc的部落格

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

題目大意:  鈔票m元，給x顆糖果價格，問花最多錢多少元

思路:  無限背包，跟前面題目類似。只不過1維dp可以由前往後，因為不限制

代碼:  

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

bool dp[M];
int arr[N];
int main()
{
    int m, n;
    cin >> m >> n;
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    dp[0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = arr[i]; j <= m; ++j){
            dp[j] |= dp[j-arr[i]];
        }
    }
    int x = m;
    for(; !dp[x]; x--);
    cout << x << endl;
    return 0;
}