题目大概: 用n元买书,书有10 20 50 100元的。问有多少种买书方案。 思路: 这个题是完全背包问题的方案数问题,即每一样物品是可以无限制的拿取的。 状态h[i]是i元的方案数,这个题
题目大概:
用n元买书,书有10 20 50 100元的。问有多少种买书方案。
思路:
这个题是完全背包问题的方案数问题,即每一样物品是可以无限制的拿取的。
状态h[i]是i元的方案数,这个题和数字组合非常相似。把完全背包问题变换一下就可以了。
即把完全背包的两层循环里的max(h[i],h[i-a[j]])改成h[i]+h[i-a[j]]。
感想:
无。
代码:
已整理
#include <iostream>using namespace std;
int main()
{
int n;
int a[5]= {0,10,20,50,100},h[1001]= {0};
h[0]=1;
cin>>n;
for(int i=1; i<=4; i++)
for(int j=a[i]; j<=n; j++)
{
h[j]+=h[j-a[i]];
}
cout<<h[n];
return 0;
}