【多重背包】Atcoder Beginner Contest 286----D

题目：D - Money in Hand (atcoder.jp)

分析：经典的多重背包。用dp[i]表示i能否正好凑出。先复习一下多重背包。

多重背包就是有N组物品，每组最多有k个，每组可以选多个。分组背包和多重背包类似，分组背包也是有N组，每组有K个，但分组背包中每组最多只能选一个。

对于多重背包，先枚举物品，然后枚举体积（一维倒序），然后在枚举每组选择的个数。

对于分组背包，先枚举物品，然后枚举体积（一维倒序），然后再枚举每组中选择哪个。

代码：

#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pll;
typedef unsigned long long ULL;
const ll mod = 998244353;
const int N = 2e5 + 5;
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}

int a[N];
map<int,int>mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n,x;
    int a[55],b[55];
    cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    int dp[10005];
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=x;j>=0;j--)
        {
            for(int k=0;k<=b[i];k++)
            {
                if(j>=k*a[i]&&dp[j-k*a[i]]) dp[j]=1;
            }
        }
    }
    if(dp[x]) cout<<"Yes";
    else cout<<"No";
    return 0;
}