题目描述
小明手里有n元钱全部用来买书,书的价格为10元,20元,50元,100元。
问小明有多少种买书方案?(每种书可购买多本)
算法:完全背包
时间复杂度:O($N*M$)
需要注意
(1)每个书可以选多个,所以是完全背包问题
(2)状态表示为体积恰好为j的方案的数量,所以对f[0]需要进行初始化
C++代码
#include<iostream>
using namespace std;
const int N=1010;
int f[N];
int w[]={10,20,50,100};
int main()
{
int n;
cin>>n;
f[0]=1;
for(int i=0;i<4;i++){
for(int j=w[i];j<=n;j++)
f[j]+=f[j-w[i]];
}
cout<<f[n]<<endl;
return 0;
}