题目描述
小明手里有n元钱全部用来买书,书的价格为10元,20元,50元,100元。
问小明有多少种买书方案?(每种书可购买多本)
输入格式
一个整数 n,代表总共钱数。
输出格式
一个整数,代表选择方案种数。
样例
数据范围
0≤n≤1000
输入样例1:
20
输出样例1:
2
输入样例2:
15
输出样例2:
0
输入样例3:
0
输出样例3:
1
完全背包求方案数
dp[i][j]->前i件物品中选,恰好为j的方案数
原理和完全背包一模一样
$dp[i][j]=dp[i-1][j];$
$if(j>=v[i])dp[i][j]+=dp[i][j-v[i]];$
一维优化 代码
#include <iostream>
using namespace std;
const int N=1010;
int a[5]={0,10,20,50,100};
int dp[N], n;
int main()
{
cin>>n;
dp[0]=1;
for(int i=1;i<=4;i++)
for(int j=a[i];j<=n;j++)
dp[j]+=dp[j-a[i]];
cout<<dp[n]<<endl;
}