动态规划--买书（背包方案数）

动态规划--买书（背包方案数）

题目大概：

用n元买书，书有10  20  50  100元的。问有多少种买书方案。

思路：

这个题是完全背包问题的方案数问题，即每一样物品是可以无限制的拿取的。

状态h[i]是i元的方案数，这个题和数字组合非常相似。把完全背包问题变换一下就可以了。

即把完全背包的两层循环里的max（h[i]，h[i-a[j]]）改成h[i]+h[i-a[j]]。

感想：

无。

代码：

已整理

#include 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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。