动态规划如何计算买书问题的背包方案总数？

本文共计464个文字，预计阅读时间需要2分钟。

题目概述：用n元买书，书的价格有10、20、50、100元。问有多少种买书方案。

思路：这是一个完全背包问题，即每种物品（书）可以无限次选取。状态定义：h[i]表示用i元可以买的书的方案数。

解答：这个问题可以通过动态规划来解决。我们可以定义一个数组h，其中h[i]表示用i元可以买的书的方案数。

状态转移方程为：h[i]=h[i - 10] + h[i - 20] + h[i - 50] + h[i - 100]

初始条件：h[0]=1，因为用0元可以买0本书，只有一种方案。

计算h[n]，其中n为总金额，即可得到答案。注意，由于题目要求不使用数，我们可以直接输出方案数。

题目大概：

用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;
}