题目链接：https://vjudge.net/contest/217847#problem/A
题目大意：
现在有n种硬币,每种硬币有特定的重量cost[i] 克和它对应的价值val[i]. 每种硬币可以无限使用. 已知现在一个储蓄罐中所有硬币的总重量正好为m克, 问你这个储蓄罐中最少有多少价值的硬币? 如果不可能存在m克的情况, 那么就输出” This is impossible.”.
解题分析：
由于每种硬币可以无限使用, 所以是明显的完全背包问题，dp[i][j]为只用前i种硬币装满j克的最小价值。注意最后对是否能够装满的判断。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = + ;
#define INF 1e9 int n, m;
int dp[maxn];
int weight[maxn];//每种货币重量
int val[maxn]; //每种货币价值 int main()
{
int T; cin>>T;
while (T--)
{
int m1, m2;
cin>>m1>>m2>>n;
m = m2 - m1;
for (int i = ; i <= n; i++)
cin >> val[i] >> weight[i];
for (int i = ; i <= m; i++) dp[i] = INF;
dp[] = ;
for (int i = ; i <= n; i++)
{
for (int j = weight[i]; j <= m; j++)
dp[j] = min(dp[j], dp[j - weight[i]] + val[i]);
}
if (dp[m] == INF) printf("This is impossible.\n"); //因为如果不能装满m克的话，也不能装满m-weight[i]克，因为那样再加上一个weight[i]克的硬币就装满m克了，所以dp[j-weight]+val=INF+val,所以此时dp[m]仍然为INF
else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[m]);
}
return ;
}
2018-05-16