首页 > 代码库 > hdu 1114 Piggy-Bank

hdu 1114 Piggy-Bank

2024-07-14 01:57:53   223人阅读

求最大价值：要求恰好装满背包，那么在初始化时除了dp[0]为0其它dp[1..V]均设为-∞  
  
求最小价值：要求恰好装满背包，那么在初始化时除了dp[0]为0其它dp[1..V]均设为∞

注意事项：题目要求要“恰好装满”，所以初始化时，除dp[0]赋值为零外其它的dp[i]都赋值为+∞，因为题目是求最小值，若为求最大值，则dp[i]都赋值为-∞；求最大值中若没有限定则都赋值为0；注意两种问法的不同；


代码如下：  

注意下标问题
#include<stdio.h>
int p[1008],w[1008];
int dp[10000];
int min(int a,int b)
{return a>b?b:a;}
int main()
{
   int E,F,V,T,i,j,N;
   scanf("%d",&T);
   while(T--)
   {
      scanf("%d%d",&E,&F);
      V=F-E;
      for(i=0;i<=V;i++)
      dp[i]=9999999;
      dp[0]=0;
      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]==9999999)printf("This is impossible.\n");
      else
        printf("The minimum amount of money in the piggy-bank is %d.\n", dp[V]);  
   }
    return 0;
}



联系
我们