外卖(dp)

题目链接:http://icpc.upc.edu.cn/problem.php?id=19273

题目
Bob 是一个重度外卖依赖者。这天他挑中了一家店，这家店总共有 n n n 种菜品，每种菜品限点一份，需要满 m m m 元钱才可配送，因此 Bob 想知道他至少需要花多少钱才能满足最低配送要求。

输入
输入共两行，第一行为两个正整数， n n n 和 m m m，第二行为 n n n 个正整数 a i a_i ai​

输出
输出一个数，满足最低配送要求所花的最少钱数。

样例输入：

【样例1】

3 10 
3 7 9

【样例2】

5 12 
10 11 7 8 9

【样例3】

3 8 
1 6 9 

样例输出：

【样例1】

10

【样例2】

15

【样例3】

9

提示
对于第二个样例，最低配送要求为 12 12 12 元，最优解为点 7 7 7 块和 8 8 8 块的两个菜，最少花 15 15 15 元。

对于 30 30% 30 的数据，满足 n ≤ 15 n ≤ 15 n≤15 。
对于 100 100% 100 的数据，满足 n ≤ 200 n ≤ 200 n≤200， m ≤ m ≤ m≤ 所有ai的和 ≤ 50000 ≤ 50000 ≤50000 。

和砝码称重类似

用 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 种菜品能否表示价格 j j j

对于每种菜品有 2 2 2 种选法，
1. 1. 1. 不买 此时 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i - 1][j] dp[i][j]=dp[i−1][j]
2. 2. 2. 买 ( + a r r [ i ] ) (+arr[i]) (+arr[i]) 此时 d p [ i ] [ j ] = d p [ i − 1 ] [ j − a r r [ i ] ] dp[i][j] = dp[i - 1][j - arr[i]] dp[i][j]=dp[i−1][j−arr[i]]

第一种选法一定有，第二种选法要判断 j − a r r [ i ] j - arr[i] j−arr[i] 是否 > = 0 >= 0 >=0

AC代码

#include 
 
using namespace std;
 
const int N = 210,M = 50010;
 
int n,m;
int arr[N];
bool dp[N][M];
 
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> arr[i];
 
    dp[0][0] = true;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < M; j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j - arr[i] >= 0)dp[i][j] |= dp[i-1][j - arr[i]];
        }
    }
    for(int j = m; j < M; j++)
    {
        if(dp[n][j])
        {
            cout << j << endl;
            break;
        }
    }
    return 0;
}