POJ 1384 Piggy-Bank（完全背包，裸题）

题目意思：
给你一个储蓄罐空的，和满的重量，然后给出各种硬币的价值和对应的重量，
要你估计出储蓄罐里面硬币价值和最小为多少，注意要保证重量和恰好为给出满的重量。

本题要点：
1、完全背包的裸题：
背包容量，就是储蓄罐中硬币的重量（满罐 - 空罐）;
物品的体积，就是硬币的重量;
物品的价值，就是硬币的面值。
2、dp[i] 表示体积为i的背包，能装的物品最小价值之和
转态转移：
dp[j] = min(dp[j], dp[j - v[i]] + w[i]); // 能装下 v[i]时候，取较小值

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 510, MaxM = 10010;
int T, n, w1, w2, m;
int v[MaxN], w[MaxN];	//体积，价值
int dp[MaxM];	//dp[i] 表示体积为i的背包，能装的物品最小价值之和int main()
{
    scanf("%d", &T);while(T--){
    scanf("%d%d", &w1, &w2);scanf("%d", &n);for(int i = 1; i <= n; ++i){
    scanf("%d%d", &w[i], &v[i]);}m = w2 - w1;memset(dp, 0x3f, sizeof dp);	//因为取较小值，所以 dp 初始化为 大值dp[0] = 0;for( int i = 1; i <= n; ++i){
    for(int j = v[i]; j <= m; ++j){
    dp[j] = min(dp[j], dp[j - v[i]] + w[i]);}}if(dp[m] == 0x3f3f3f3f){
    printf("This is impossible.\n");}elseprintf("The minimum amount of money in the piggy-bank is %d.\n", dp[m]);}return 0;
}/* 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. */