本文共 2992 字，大约阅读时间需要 9 分钟。
做这道题前得先知道一件事情，就是怎么把多重背包转换为01背包。
我就讲一下二进制划分的方法，先举一个例子，给你100张1元硬币，让你凑10元钱，按照咱们常识是数十张，但是这效率太低了，计算机不一样，计算机不需要1张1张的数，它可以1，2，4，8的数，这样就能快速的凑够10元，当到8的时候，总数为15，超过了10，那么到4后就停下，剩下的3个看作一个整体。这就是二分划分思想。官方的话我就不复制粘贴了，一百度一堆。 当多重背包的时候，你有n个同样的物品，这时候物品就相当于上面的一元钱，如果按照老套的计算的话，时间复杂度太大了。下面通过代码理解。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, …,CNOutput
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元。（网上的证明）证明如下： 如果买家的付款数大于了ww+m，即付硬币的数目大于了w，根据鸽笼原理，至少有两个的和对w取模的值相等，也就是说，这部分硬币能够用更少的w来代替
对于约翰来说，金币是有个数的，所以用多重背包，而店主是没有的金币是没有个数限制的，用完全背包，然后二者一结合取最小就可以了，如果取不到最下，即结果不存在，输出-1.
还是来看代码理解： ac代码：#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
转载地址：http://igaq.baihongyu.com/