Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1114
Problem Description
Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it’s weight in grams.
Output
Print exactly one line of output for each test case. The line must contain the sentence “The minimum amount of money in the piggy-bank is X.” where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line “This is impossible.”.
Sample Input
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output
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.
题目大意是这样的，给你一个罐子的自身重量和它最大的承受重量，再给你n种面值的硬币，接下来n行为每个硬币的价值和重量，（每个硬币的数量无限）让你求能恰好装满罐子的最小价值。。。如果没办法恰好装满则输出This is impossible.
这道题和我们的01背包非常像，只不过01背包只能取一次，而这道题的物品数量是无限的，那么我们对一种物品就有了非常多的选择了，不选，选1个、2个……而我在之前的01背包讲解中讲过为什么要对重量倒着操作的的原因
for (int j = v; j >=b[i]; j–)
dp[j] = max(dp[j], dp[j - b[i]] + a[i]);
正着操作的话，就会将这一次的结果重复，即多次选择该物品。倒着操作的话就是对上一次的结果加上本次的考虑。也许大家也想到了，只要倒着操作01背包，01背包就直接转化成了完全背包了，就是这么简单。。。。
for (int i=1; i<=num; i++)
for (int j=weight[i]; j<=bag; j++)
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
这就是完全背包的一个模板，正着操作，对本次的情况考虑是否+1，重复考虑第i件物品。
emmm。。。当然完全背包理解了，这一题对于萌新来说可能还是有一点蒙的，它要恰好装满，而且求最小值。我们的背包一般是求最大值的，因为我们的dp中刚开始存的都是0，所以只能求max，那么要求最小值的话只要将dp的初始状态赋值为inf（最大值）就好了，至于是否刚好装满，我们可以直接判断是否dp[bag]=inf就ok了，可能会有点疑惑，但我们可以想一想，如果不能刚好装满的话dp[bag-k*weight[i]]是不存在的为其初始值inf。那么dp[bag]就永远无法更新。。。
好了，接下来就是代码了：
#include <cstdio>
#include <cstring>
#define inf 999999999
using namespace std;
int a[505],b[505],dp[10050];
int min(int a,int b)
{
return a<b?a:b;
}
int main() {
int t,e,f,n;
scanf ("%d",&t);
while (t--) {
scanf ("%d%d",&e,&f);
scanf ("%d",&n);
for (int i=1; i<=n; i++)
scanf ("%d%d",&a[i],&b[i]);
f-=e;
for (int i=1; i<=f+10; i++)
dp[i]=inf;
dp[0]=0;
for (int i=1; i<=n; i++)
for (int j=b[i]; j<=f; j++)
dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
if (dp[f]==inf) printf ("This is impossible.\n");
else printf ("The minimum amount of money in the piggy-bank is %d.\n",dp[f]);
}
return 0;
}
那么接下来就是对完全背包的另外的两种解法了，准确的说是一种解法及其优化。
我们可以用01背包来做完全背包，这是没有毛病的。
我们对每个物品取bag/w[i]个（每个物品的最多取数）
for (int i=1; i<=bag/w; i++)
value[num++]=v,weight[i]=w;
然后就是01背包了，num中的每一个进行判断,详情请看代码：
#include <cstdio>
#include <cstring>
#define inf 999999999
using namespace std;
int a[5000005],b[5000005];
int dp[10005];
int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
int t,e,f,n;
scanf ("%d",&t);
while (t--) {
scanf ("%d%d",&e,&f);
scanf ("%d",&n);
f-=e;
int v,w,num=1;
for (int i=1; i<=n; i++){
scanf ("%d%d",&v,&w);
for (int i=1; i<=f/w; i++){
a[num]=v;b[num++]=w;
}
}
for (int i=1; i<=f+10; i++)
dp[i]=inf;
dp[0]=0;
for (int i=1; i<=num-1; i++)
for (int j=f; j>=b[i]; j--){
dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
}
if (dp[f]==inf) printf ("This is impossible.\n");
else printf ("The minimum amount of money in the piggy-bank is %d.\n",dp[f]);
}
return 0;
}
然后我们可以想象一下，其时间复杂度是比较高的，为：
然后不出所料：
超时了。。。
但不用沮丧，我们还有一个黑科技：二进制优化。01背包之所以超时就是因为对V/w[i]枚举的时间太多了，如果w[i]=1那么其所需要的时间就非常恐怖了。。那么我们可以使用二进制的思想，任何数都可以表示成01的组合，那么我们就只需取2^ 0、2^ 1……就ok了，时间复杂就降为
for (int i=1; i<=num; i++){
int k=0;
while (w*pow(2,k)<=v){
weight[tot]=w*pow(2,k);
value[tot++]=v*pow(2,k);
k++;
}
}
话不多说，贴代码了：
#include <cstdio>
#include <cstring>
#define inf 999999999
using namespace std;
int a[5000005],b[5000005];
int dp[10005];
int min(int a,int b) {
return a<b?a:b;
}
int pow(int x,int y)
{
int sum=1;
for (int i=1; i<=y; i++) sum*=x;
return sum;
}
int main() {
int t,e,f,n;
scanf ("%d",&t);
while (t--) {
scanf ("%d%d",&e,&f);
scanf ("%d",&n);
f-=e;
int v,w,tot=1;
for (int i=1; i<=n; i++) {
scanf ("%d%d",&v,&w);
int k=0;
while (w*pow(2,k)<=f) {
a[tot]=v*pow(2,k);
b[tot++]=w*pow(2,k);
k++;
}
}
for (int i=1; i<=f+10; i++)
dp[i]=inf;
dp[0]=0;
for (int i=1; i<=tot-1; i++)
for (int j=f; j>=b[i]; j--) {
dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
}
if (dp[f]==inf) printf ("This is impossible.\n");
else printf ("The minimum amount of money in the piggy-bank is %d.\n",dp[f]);
}
return 0;
}
虽然速度比之前快很多，但比起原始的完全背包解法还是有一定的差距，不过二进制优化在很多地方都用得到，也算是各有优缺吧！