本文共 2992 字，大约阅读时间需要 9 分钟。

做这道题前得先知道一件事情，就是怎么把多重背包转换为01背包。

void slove(){	memset(dp, 0, sizeof(dp));	for (int i=1; i<=n; i++)	{		if (num[i] * weight[i] >= packweight) //这里可以进行优化，此时物品的质量可以看作无穷大，相当于完全背包，也可以理解为个数无穷多。  		{			for (int j=weight[i]; j
   
    =k*weight[i]; j--)				{					dp[j] = max(dp[j], dp[j-k*weight[i]] + k*value[i]);				}				ncount -= k;				k*=2;			}			//把剩下的看作一个整体			for (int j=packweight; j>=ncount*weight[i]; j--)			{				dp[j] = max(dp[j], dp[j-ncount*weight[i]] + ncount*value[i]);			}		}	}}
   

DescriptionFarmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, …, VN (1 ≤ Vi ≤ 120). Farmer John is carrying C1 coins of value V1, C2 coins of value V2, …, and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner (although Farmer John must be sure to pay in a way that makes it possible to make the correct change).

Input

Line 1: Two space-separated integers: N and T.

Line 2: N space-separated integers, respectively V1, V2, …, VN coins

(V1, …VN)

Line 3: N space-separated integers, respectively C1, C2, …,CN

Output

Line 1: A line containing a single integer, the minimum number

of coins involved in a payment and change-making. If it is impossible

for Farmer John to pay and receive exact change, output -1.

可以注意到，上界为ww+m（w最大面额的纸币），也就是24400元。（网上的证明）证明如下：

对于约翰来说，金币是有个数的，所以用多重背包，而店主是没有的金币是没有个数限制的，用完全背包，然后二者一结合取最小就可以了，如果取不到最下，即结果不存在，输出-1.

#include 
   
    #include 
    
     using namespace std;const int INF = 0x3f3f3f3f;int dp1[25000];  //约翰对不同金额所付的最少硬币数量 int dp2[25000];  //店长对不同金额所付的最少硬币数量 int v[105], w[105];void wq(int w, int sum){	for (int i=w; i<=sum; i++)	{		dp2[i] = min(dp2[i], dp2[i-w]+1);	}}void dc(int v, int w, int sum){	if (v*w >= sum)   //如果总钱数比sum还要大，直接用完全背包做  	{		for (int i=w; i<=sum; i++)  		{        //如果用了这个硬币就把个数+1   			dp1[i] = min(dp1[i], dp1[i-w]+1);  		} 	}	else	{	  	int k = 1;	  	  	while (k < v)   //利用二进制将多重背包转换为01背包 	  	{	   		for (int i=sum; i>=k*w; i--)	   		{    //用了k个硬币，所以应该加k	    			dp1[i] = min(dp1[i], dp1[i-k*w]+k);	   		}	   	  		 v-=k;	   		k*=2;	  	}	  	//剩下的看作一个整体   		for (int i=sum; i>=v*w; i--)  		{   			dp1[i] = min(dp1[i], dp1[i-v*w]+v);  		} 	}}int main(){ 	int n, t;  	scanf("%d %d", &n, &t);  	int sum = 0;  	for (int i=0; i