背包问题2（完全背包）

01背包是指每件物品有且只有一件，而完全背包则是每件物品件数无限，求装入背包所对应的最值。
完全背包也有公式，在01背包公式的基础上加以改动。

完全背包公式：dp [ j ] =min/max( dp[ j ] ,dp [ j - w [ i ] ] + v [ i ] ) 。

从公式看出，完全背包相较于01背包，dp数组由二维变成一维，但整个过程和01背包大同小异。第一步仍然是对数组进行初始化操作，题目不同初始化操作不同，求最大值需要将dp[ ]全设为无穷小，求最小值则初始化为无穷大。公式本身不难理解，j还是代表重量为j，i是外层循环，表示目前装到第i种物品。dp[ j - w[ i ] ]就是当重量为j时少装一件物品i时的最高价值，那么装了物品i后，价值自然变为dp[ j - w[ i ] ] + v[ i ]，与当前dp[ j ]比较取符合题意的结果即可。
给出一道例题加以分析。
典例：http://acm.hdu.edu.cn/showproblem.php?pid=1114
题意：给出存钱罐空时的重量和装满时的重量，给出n种钱币的价值和重量，求存钱罐装满时所能达到的最小价值
分析：从第一个开始遍历，从重量 j >=w[ i ] 开始计算，比较装下物品 i 后的价值和没装 i 时的价值选最优解。因为背包必须装满，故最终输出dp[ full - Empty ]的价值。

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define INF 1000000001
using namespace std;
int w[505],v[505],dp[10005];
int main()
{
    int T,n,m,Empty,full;
    cin>>T;
    while(T--)
    {
        cin>>Empty>>full;
        m=full-Empty;     //m表示存钱罐能装钱币的重量
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>v[i]>>w[i];
        }
        dp[0]=0;
        for(int i=1;i<=m;i++)//dp数组初始化
            dp[i]=INF;
        for(int i=1;i<=n;i++)  //i从1到n表示n种钱币
            for(int j=w[i];j<=m;j++)  //注意j从w[ i ]开始，不然会 
                dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
        if(dp[m]<INF) cout<<"The minimum amount of money in the piggy-bank is "<<dp[m]<<"."<<endl;
        else cout<<"This is impossible."<<endl;
    }
    return 0;
}