题目描述

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

样例

输入:20
输出:2

解析

• 本题为一道完全背包求方案数的题目,建议复习完全背包模板

• 思路:
  1.f[i][j]:考虑前i个物品,总体积不超过m的买书总方案数
  2.考虑是否选择第i个物品,f[i][j]=f[i-1]j+f[i]j-v[i]*k

• 转移方程推导

f[i][j]=f[i-1][j]+f[i-1][j-v[i]*1]+f[i-1][j-v[i]*2]+...+f[i-1][j-v[i]*k];
f[i][j-v[i]]=     f[i-1][j-v[i]]+  f[i-1][j-v[i]*2]+...+f[i-1][j-v[i]*k];
=>f[i][j]=f[i-1][j]+f[i][j-v[i]];

代码如下

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;

int n,m;
int v[5]={0,10,20,50,100};
int f[N];

int main(){
    n=4;
    scanf("%d",&m);

    f[0]=1;//初始赋值！ 
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=m;j++){
            f[j]=f[j]+f[j-v[i]];//选与不选第i个物品的可行方案数的总和 
        }
    }

    printf("%d",f[m]);

    return 0;
}