动态规划--数字组合（背包方案数）

题目大概：

输入一个数字t，  输入n个数子，用这n个数有多少种组合成数字t的方案（每个数字只能用一次）。

思路：

读完题后，感觉这个题是背包的方案数问题。并且这个题是一个物品只能用一次的背包，即01背包问题变化的方案数问题。

状态：a[i]表示用这些数字组成数字 i 所有的方案数。一直从1到t。

然后只需要把01背包的思路改动一下，就可以完成这个题了。

01背包第一层循环int y=1....n  表示第一个数到第n个数。

第二层循环int j=t....1  表示组成的数字。

只需把两层循环里的max（a[i]，a[i-j]）改成a[i]+a[i-j]即可。

感想：

原来只要掌握基本背包问题，一些变换的题型也可以解决。

代码：

已整理

#include <iostream> using namespace std; int main() { int n,m; int a[21]= {0}; int h[1001]= {0}; h[0]=1; cin>>n>>m; for(int i=1; i<=n; i++) { cin>>a[i]; } for(int i=1; i<=n; i++) { for(int t=m; t>=1; t--) { if(t>=a[i]) { h[t]=h[t]+h[t-a[i]]; } } } cout<<h[m]; return 0; }