# HDU 1114 Piggy-Bank 猪仔储钱罐（AC代码）完全背包（容量需满，价值最小）

``` 1 #include <iostream>
2 #define MAX 0xfffffff
3 using namespace std;
4 //要求：1、刚好装满    2、总价值最小
5 int value[501];
6 int weight[501];
7 int dp[10010];
8 int min(int a,int b)
9 {
10     return a<b?a:b;
11 }
12 int cal(int v,int n)    //空间、种类
13 {
14     int i,j;
15     dp[0]=0;
16     for(i=1;i<=v;i++)
17         dp[i]=MAX;
18     for(i=1;i<=n;i++)
19         for(j=weight[i];j<=v;j++)
20         {
21                 dp[j]=min( dp[j] , dp[j-weight[i]] + value[i] );
22         }
23     return dp[v];
24 }
25 void main()
26 {
27     int T;
28     scanf("%d",&T);
29     int E,F,N,ans;
30     while(T--)
31     {
32         int i;
33         scanf("%d%d",&E,&F);    //空罐、满罐
34         scanf("%d",&N);            //多少种硬币
35         for(i=1;i<=N;i++)
36         {
37             scanf("%d%d",&value[i],&weight[i]);    //价值、重量
38         }
39         ans=cal(F-E,N);
40         if(ans==MAX)
41             printf("This is impossible.\n");
42         else
43             printf("The minimum amount of money in the piggy-bank is %d.\n",ans);
44     }
45 }```

1114

## hdu 1028 Ignatius and the Princess III（母函数，完全背包）

http://acm.hdu.edu.cn/showproblem.php?pid=1028 整数划分问题. 第一道母函数...母函数入门 小于等于n的整数共有n个,1,2......n,每个数都有无限多个,对于整数1,它所对应的母函数为(1+x+x^2+...+x^k+...),整数2对应的母函数为(1+x^2+X^4+...+x^(2*k)+...),整数3对应的母函数为(1+x^3+x^6+...+x^(3*k)+...),以此类推,直到整数n. 那么n的整数划分的个数就是这n个母函数乘积

## HDU 4738 Caocao&#39;s Bridges（求价值最小的桥）

Problem Description Caocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn't give up. Caocao's army still was not good at water battles, so he came up with another idea. He built many islands in the Changjiang river, and