题目大意：
T组数据，每组数据一个n，代表n种类型的硬币，首先给你E,F,然后F-E代表背包可容纳总重量，下面给出n种硬币的价值wiwi和重量vivi,每种不限数量，问装满可容纳F-E重量的背包硬币价值最小是多少。如果不能，则输出This is impossible.
数据范围：
1≤n≤500,1≤E≤F≤10000,1≤wi≤50000,1≤vi≤10000.1≤n≤500,1≤E≤F≤10000,1≤wi≤50000,1≤vi≤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#include #include #include #include #include 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.\n");//如果值未改变，说明不存在该状态 else printf("The minimum amount of money in the piggy-bank is %d.\n", dp[W]); } return 0;}