哈理工OJ 1627 猪猪罐（完全背包）

题目链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1627

猪猪罐
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 39(21 users) Total Accepted: 23(21 users) Rating: Special Judge: No
Description
ikki有一个小金库，这是一个猪猪罐，猪猪罐里面放了一些硬币。ikki知道了每种硬币的价值和重量，并且还知道空猪猪罐的重量，现在ikki想知道这个猪猪罐里至少放了价值为多少的硬币，她只能称出整个猪猪罐的总重量，你能帮她计算一下么？

Input
多组测试数据，第一行给出一个整数T表示测试数据的组数。

对于每组数据：

第一行输入两个正整数E、V，其中E表示空猪猪罐的重量，V表示放了硬币之后猪猪罐的总重量。（1<=E<=V<=10000）

第二行输入一个整数N表示硬币的种数。（1<=N<=50）

接下来的N行，每行两个整数v，w分别表示每种硬币的价值和重量。（1<=v<=50000,1<=w<=10000）

Output
对于每组数据输出猪猪罐中硬币价值可能的最小值，如果不存在则输出”Impossible”。

每组输出占一行。
Sample Input
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output
60
100
Impossible

【题目分析】本题是一道完全背包的题目，一开始想了好久好久，因为这个背包和平常遇到的完全背包有区别，因为这个背包是知道了最终的重量，然后让你求是不是可以由某些硬币组成，假如可以由某些硬币组成的话，找出价值和最小的那一组硬币。可以一开始给dp数组置一个很大的数。
【AC代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1000005

struct node
{
    int val,cost;
}a[55];

int dp[10005];

int main()
{
    int t,e,v,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&e,&v);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].val,&a[i].cost);
        }
        v=v-e;
        for(int i=1;i<=v;i++)
        {
            dp[i]=INF;
        }
        dp[0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=a[i].cost;j<=v;j++)
            {
                if(dp[j-a[i].cost]!=INF)
                {
                    dp[j]=min(dp[j-a[i].cost]+a[i].val,dp[j]);
                }
            }
        }
        if(dp[v]!=INF)
        printf("%d\n",dp[v]);
        else
        printf("Impossible\n");
    }
    return 0;
}