ABC286D多重背包凑面额

#include <stdio.h>
int n, m, i, j, k, c, v, f[10005];
int main(){
    scanf("%d%d", &n, &m);
    f[0] = 1;
    for(i=1; i<=n; i++){
        scanf("%d%d", &v, &c);
        while(c--){
            for(j=m; j>=v; j--){
                f[j] |= f[j-v];
            }
        }//拆分乘c个01背包
    }//多重背包模板
    printf("%s\n", f[m]?"Yes":"No");
    return 0;
}

记忆化搜索做法：

#include <stdio.h>
int n, m, i, j, k, ok;
int a[55], c[55], f[55][10005];
void dfs(int k, int s){
    int i, j;
    if(s == m) ok = 1;
    if(ok) return;
    if(s > m) return;
    if(k > n) return;
    if(f[k][s]) return;
    f[k][s] = 1;//记忆化
    for(i=0; i<=c[k]; i++){
        dfs(k+1, s+i*a[k]);
    }//暴力枚举每种面额用多少个 
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d%d", &a[i], &c[i]);
    }
    dfs(1, 0);
    printf("%s\n", ok?"Yes":"No");
    return 0;
}