hdu1114Piggy-Bank(DP完全双肩包)

hdu1114Piggy-Bank(DP完全背包)

题意:在ACM可以做任何事情,必须准备和预算获得必要的财政支持。这次行动的主要收入来自不可逆绑定金钱(IBM)。背后的想法很简单。每当一些ACM成员有任何小的钱,他把所有的硬币和成小猪银行抛出。你知道,这个过程是不可逆的,不能被删除的硬币没有打破猪。足够长的时间后,应该有足够的现金在小猪银行支付,需要支付的一切,但有一个很大的问题,小猪银行。这是不可能的,以确定多少钱,里面是。因此,我们可能会破坏猪成片,才发现没有足够的钱。显然,我们要避免这种不愉快的情况。唯一的可能性是衡量小猪银行,并尝试猜里面有多少硬币。假设我们能够准确,我们知道所有硬币给定货币的权重确定权重的猪。再有就是一些最低金额在小猪银行的钱,我们可以保证。你的任务是要找出这种最坏的情况下,里面的小猪银行确定的最低数额的现金。我们需要你的帮助。没有更多的过早破裂的猪!

输入包括T检验案件。它们的数量(T)给定的输入文件的第一行上。每个测试案例开始行包含两个整数E和F表示一个空的猪和猪装满硬币的重量。两个权重给定的以克为单位。没有猪的重量超过10公斤,这意味着1 <= E <= F <= 10000。在第二行中的每一个测试的情况下,是一个整数N(1 <= N <= 500),使在给定的货币使用的各种硬币的数目。这正是N行,每指定一个硬币型。这些行包含两个整数,P和W(1 <= P <= 50000,1 <= W <= 10000)。P是货币单位的硬币的值,W是它的重量克数。

原题:http://acm.hdu.edu.cn/showproblem.php?pid=1114
题目解析:就相当于一个容量为V的背包,开始时包里已装有重量为E的物体,然后有一些重量为W[i],价值为P[i]物品,求装满背包时用的最小钱数,

代码实现:

#include<stdio.h>
#include<cstring>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define MAX  10005
#define IFN  1000000
int dp[MAX];
int p[505],w[505];
int min(int x,int y)
{
     return(x>y?y:x);
}
int main()
{
   //freopen("input.txt","r",stdin);
     int e,v;
     int i,j,t;
     scanf("%d",&t);
     while(t--)
     {
          scanf("%d%d",&e,&v);
          dp[0]=0;//注意dp[0]要赋值为0;
          for(i=1;i<=v;i++)dp[i]=IFN;
          v-=e;
          int n;
          scanf("%d",&n);
          for(i=0;i<n;i++)
                scanf("%d%d",&p[i],&w[i]);
          for(i=0;i<n;i++)
          for(j=w[i];j<=v;j++)
          {
               dp[j]=min(dp[j],dp[j-w[i]]+p[i]);
          }
          if(dp[v]==IFN)printf("This is impossible.\n");
          else
          printf("The minimum amount of money in the piggy-bank is %d.\n",dp[v]);

     }
   return 0;
}