HDU

Piggy-Bank

题目大意：

T组数据，每组数据一个n，代表n种类型的硬币，首先给你E,F,然后F-E代表背包可容纳总重量，下面给出n种硬币的价值wi$w_i$和重量vi$v_i$,每种不限数量，问装满可容纳F-E重量的背包硬币价值最小是多少。如果不能，则输出This is impossible.

数据范围：

1≤n≤500,1≤E≤F≤10000,1≤wi≤50000,1≤vi≤10000.$1\le n\le 500,1\le E\le F\le 10000,1\le w_i\le 50000,1\le v_i\le 10000.$

解题思路：

题意可简化为，n种物品，每种无数个，装满W重量的背包的最小价值，这是一个完全背包的题，dp[j]代表承重为j的背包的最小价值，转移方程为：

dp[j]=max(dp[j],dp[j−v[i]]+w[i])$$dp[j]=max(dp[j],dp[j-v[i]]+w[i])$$

具体见代码

AC代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10000;
const int INF = 1e9 + 7;
int dp[maxn + 5];
int E, F, W;
int T, n;
int w[505], v[505];
int main() {
    scanf("%d", &T);
    while(T--) {
        for(int i = 0; i <= maxn; i++)dp[i] = INF;//初始化为无穷大
        scanf("%d%d", &E, &F);
        W = F - E;//背包大小
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)scanf("%d%d", &w[i], &v[i]);
        dp[0] = 0;
        for(int i = 1; i <= n; i++) {//虽然每个物体有无限个，但是对于第i个物体，dp[j]可由dp[j-v[i]]转移过来，就达到了取任意多个第i种物体之后的状态
            for(int j = v[i]; j <= W; j++) {
                dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
            }
        }
        if(dp[W] == INF)printf("This is impossible.
");//如果值未改变，说明不存在该状态
        else printf("The minimum amount of money in the piggy-bank is %d.
", dp[W]);
    }
    return 0;
}