OI

【动态规划】背包？

P1164小A点菜

类似于背包：

f[i][j]为前i件j元的方法数，则
$f[i][j]= f[i-1][j]+f[i-1][j-a[i]]$……$ (j>a[i])$
$f[i][j]= f[i-1][j]+f[i-1][j]+1$……$ (j=a[i])$
$f[i][j]= f[i-1][j]$……$ (j<a[i])$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=105,MAXM=10005;
int a[MAXN],f[MAXN][MAXM]={0};

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(j==a[i])f[i][j]=f[i-1][j]+1;
            if(j>a[i]) f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
            if(j<a[i]) f[i][j]=f[i-1][j];
        }
    
    printf("%d",f[n][m]);
    
    return 0;
}

然后可以优化成一维：

1
2
3
4
5
6
7
for(int i=1;i<=n;i++)
    for(int j=m;j>=a[i];j--){
        if(j==a[i])f[j]=f[j]+1;
        if(j>a[i]) f[j]=f[j]+f[j-a[i]];
    }
    
printf("%d",f[m]);