机试算法讲解：第55题 Piggy-Bank

/*
问题:与一个储蓄罐，告知空的质量和当前重量，并给定一些钱币的价值和相应的重量，求储蓄罐中最少有多少现金。
输入:包含T组测试用例。第一行。每一个测试用例包含2个整数E和F，表明空储蓄罐的重量和装满钱的重量。<=10,000g，第二行是每个测试用例，包含一个整数N(1<=N<=500)，
     给出了各种硬币的数量。接下来是N行，每行表示一种硬币类型，每行包括2个整数，P,W(1<=p<=50000,1<=W<=10000)，p是价值，W是重量
输出:
储蓄罐中最少有多少钱
输入
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2 
10 3
20 4
输出:
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

分析:完全背包问题的变体。1不求最大值，求最小值。则程序中选择价值小的那个，2要求钱币和空储蓄罐的重量恰好达到总重量，在背包问题中表现为背包恰好装满。
关键:
1 由于你获取物品的时候是从i = 1开始获取的，因此背包计算的时候i也必须从1开始遍历


参考: 
计算机考研--机试指南
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INT_MAX 0x7fffffff
#define N 10001
typedef struct List
{
 int w;//体积
 int v;//价值
}List;

int min(int a,int b)
{
 return a < b ? a : b;
}

int main(int argc,char* argv[])
{
 int T;//测试用例数
 int iEmp;//空储蓄罐重量
 int s;//装满前的储蓄罐重量
 int n;//n行
 int i,j;
 while(EOF!=scanf("%d",&T))
 {
  while(T--)
  {
   List list[501];//最多一共会出现500中货币
   int dp[N];
   scanf("%d %d",&iEmp,&s);
   s -= iEmp;//求出钱的重量
   scanf("%d",&n);
   //获取输入的钱
   for(i = 1 ; i <= n ; i++)
   {
    scanf("%d %d",&list[i].v,&list[i].w);
   }
   //初始化完全背包，除dp[0]外其余状态均不存在
   for(i = 0 ; i <= s ;i++)
   {
    //dp[i] = -INT_MAX;
    dp[i] = INT_MAX;
   }
   dp[0] = 0;
   //开始背包计算,注意遍历所有物品从物品1开始计算，因为物品0根本没有复制
   //for(i = 0 ; i <= n ; i++)
   for(i = 1 ; i <= n ; i++)
   {
    //完全背包：顺序
    for(j = list[i].w ; j <= s; j++)
    {
     //易错，需要判断状态是否可以得到
     //if(-INT_MAX!=dp[j-list[i].w])
     if(INT_MAX!=dp[j-list[i].w])
     {
      dp[j] = min(dp[j],dp[j-list[i].w]+list[i].v);
     }
    }
   }
   //如果状态不可得
   //if(-INT_MAX==dp[s])
   if(INT_MAX==dp[s])
   {
    puts("This is impossible.");
   }
   else
   {
    printf("The minimum amount of money in the piggy-bank is %d\n",dp[s]);
   }
  }
 }

 system("pause");
 getchar();
 return 0;
}

机试算法讲解： 第55题 Piggy-Bank

机试算法讲解：第55题 Piggy-Bank