子集和问题（应用--换零钱）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,dp[32800],w[4];
int main()
{
    w[1]=1;
    w[2]=2;
    w[3]=3;
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=1; i<=3; i++)//依次添加每类货币
    {
        for(int j=i; j<=32768; j++)//枚举可使用第i类货币每一种可能的数和
        {
            dp[j]=dp[j]+dp[j-w[i]];// （累计前i-1类货币构成j-w[i]的方式数）
            //dp[j]=dp[j]+dp[j-w[i]]的含义为：使用前i类货币时的货币组成可能可能的数(dp[j])=当使用前i-1类货币时的货币组成可能的数(dp[j])
            //+选择使用一个i类货币+剩余钱数（j-w[i])组成的货币的数目（前i类）---这里有点背包的感觉，所以说他是背包的应用
        }
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",dp[n]);
    }
    return 0;
}