http://poj.org/problem?id=3260
题意：John去买东西，东西的价格是T(1 <= T <= 10000)，John所在的地方有n(1 <= n <= 100)种的硬币，面值分别为V1, V2, ..., Vn (1 <= Vi <= 120)。John带了C1枚面值为V1的硬币，C2枚面值为V2的硬币，...，Cn枚面值为Vn的硬币(0 <= Ci <= 10000)。售货员那里每种硬币都有无限多个。问为了支付这个T，John给售货员的硬币数目加上售货员找回的零钱的硬币数目最少是多少。如果无法支付 T，输出-1 。
解法：支付时硬币数量有限制，为多重背包问题，通过二进制方法转化为01背包求解。找零时，硬币数量无限制，为完全背包问题。对两问题分别求解，然后找出差额为T时，两者和的最小值即为所示。
其中：给钱上界为：T+maxValue^2，其中maxValue为最大硬币面值。证明：反证法。假设存在一种支付方案，John给的钱超过 T+maxValue^2， 则售货员找零超过maxValue^2，则找的硬币数目超过maxValue个，将其看作一数列，求前n项和sum(n)，根据鸽巢原理，至少有两 个对maxValue求模的值相等，假设为sum(i)和sum(j),i<j，则i+1...j的硬币面值和为 maxValue的倍数，同理，John给的钱中也有 一定数量的硬币面值和为maxValue的倍数，则这两堆硬币可用数量更少的maxValue面值硬币代替，产生更优方案。
分析：1.给钱时，硬币数有限制，为多重背包问题。
2.找钱时，硬币数无限制，为完全背包问题。
3.给钱上界为：T+maxValue^2，其中maxValue为最大硬币面值。证明：反证法。假设存在一种支付方案，John给的钱超过T+maxValue^2，
则售货员找零超过maxValue^2，则找的硬币数目超过maxValue个，将其看作一数列，求前n项和sum(n)，根据鸽巢原理，至少有两
个对maxValue求模的值相等，假设为sum(i)和sum(j),i<j，则i+1j的硬币面值和为maxValue的倍数，同理，John给的钱中也有
一定数量的硬币面值和为maxValue的倍数，则这两堆硬币可用数量更少的maxValue面值硬币代替，产生更优方案。
http://www.cnblogs.com/xcw0754/p/4493874.html
支付时硬币数量有限制，为多重背包问题，通过二进制方法转化为01背包求解。找零时，硬币数量无限制，为完全背包问题。对两问题分别求解，然后找出差额为T时，两者和的最小值即为所示。
int main() 26
{ 27
int N,T,n; 28 int maxV,maxT,minC; 29 30 while(cin>>N>>T) 31
{ 32 maxV = 0; 33 for(int i=1; i<=N; i++) 34 { 35 cin>>V[i]; 36 if(maxV < V[i]) //找出最大面值硬币
37 { 38 maxV = V[i]; 39
}
40 }
41 maxV *= maxV; 42 maxT = T + maxV; //给钱的上界maxT=T+max_Value^2
43 for(int i=1; i<=N; i++) 44 { 45 cin>>C[i]; 46 }
47 48 n = 0; 49 for(int i=1; i<=N; i++) //二进制方法，将多重背包问题转化为01背包问题
50 { 51 for(int j=0; (1<<j)<=C[i]; j++) 52 { 53 ++n; 54 dV[n][1] = 1<<j; 55 dV[n][0] = dV[n][1] * V[i]; 56 }
57 if(C[i] > 1) 58 { 59 dV[n][1] = C[i] - dV[n][1] + 1; 60 dV[n][0] = dV[n][1] * V[i]; 61 }
62 }
63 64 for(int j=0; j<=maxV; j++) //找零dp过程，完全背包
65 { 66 dpC[j] = INF; 67 }
68 dpC[0] = 0; 69 for(int i=1; i<=N; i++) 70 { 71 for(int j=V[i]; j<maxV; j++) //从小到大
72 { 73 if(dpC[j] > dpC[j-V[i]] + 1) 74 { 75 dpC[j] = dpC[j-V[i]] + 1; 76 }
77 }
78 }
79 80 for(int j=0; j<=maxT; j++) //给钱dp过程，01背包
81 { 82 dpF[j] = INF; 83 }
84 dpF[0] = 0; 85 86 for(int i=1; i<=n; i++) 87 { 88 for(int j=maxT; j>=dV[i][0]; j--) //从大到小
89 { 90 if(dpF[j] > dpF[j-dV[i][0]] + dV[i][1]) 91 { 92 dpF[j] = dpF[j-dV[i][0]] + dV[i][1]; 93 }
94 }
95 }
96 97 minC = INF; 98 for(int j=T; j<=maxT; j++) //两个最小之和为所求
99 {100 if(minC > dpF[j] + dpC[j-T])101 {102 minC = dpF[j] + dpC[j-T];103 }
104 }
105 if(minC != INF)106 {107 cout<<minC<<endl;108 }
109 else
110 {111 cout<<"-1"<<endl;112 }
113 }
114 return 0;115
}
Read full article from 背包问题--POJ 3260 The Fewest Coins【完全背包+多重背包】 - AndreMouche - 博客园
Farmer 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 is.
FJ 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).
FJ 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
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.
背包问题--POJ 3260 The Fewest Coins【完全背包+多重背包】 - AndreMouche - 博客园题意：John去买东西，东西的价格是T(1 <= T <= 10000)，John所在的地方有n(1 <= n <= 100)种的硬币，面值分别为V1, V2, ..., Vn (1 <= Vi <= 120)。John带了C1枚面值为V1的硬币，C2枚面值为V2的硬币，...，Cn枚面值为Vn的硬币(0 <= Ci <= 10000)。售货员那里每种硬币都有无限多个。问为了支付这个T，John给售货员的硬币数目加上售货员找回的零钱的硬币数目最少是多少。如果无法支付 T，输出-1 。
解法：支付时硬币数量有限制，为多重背包问题，通过二进制方法转化为01背包求解。找零时，硬币数量无限制，为完全背包问题。对两问题分别求解，然后找出差额为T时，两者和的最小值即为所示。
其中：给钱上界为：T+maxValue^2，其中maxValue为最大硬币面值。证明：反证法。假设存在一种支付方案，John给的钱超过 T+maxValue^2， 则售货员找零超过maxValue^2，则找的硬币数目超过maxValue个，将其看作一数列，求前n项和sum(n)，根据鸽巢原理，至少有两 个对maxValue求模的值相等，假设为sum(i)和sum(j),i<j，则i+1...j的硬币面值和为 maxValue的倍数，同理，John给的钱中也有 一定数量的硬币面值和为maxValue的倍数，则这两堆硬币可用数量更少的maxValue面值硬币代替，产生更优方案。
分析：1.给钱时，硬币数有限制，为多重背包问题。
2.找钱时，硬币数无限制，为完全背包问题。
3.给钱上界为：T+maxValue^2，其中maxValue为最大硬币面值。证明：反证法。假设存在一种支付方案，John给的钱超过T+maxValue^2，
则售货员找零超过maxValue^2，则找的硬币数目超过maxValue个，将其看作一数列，求前n项和sum(n)，根据鸽巢原理，至少有两
个对maxValue求模的值相等，假设为sum(i)和sum(j),i<j，则i+1j的硬币面值和为maxValue的倍数，同理，John给的钱中也有
一定数量的硬币面值和为maxValue的倍数，则这两堆硬币可用数量更少的maxValue面值硬币代替，产生更优方案。
http://www.cnblogs.com/xcw0754/p/4493874.html
支付时硬币数量有限制，为多重背包问题，通过二进制方法转化为01背包求解。找零时，硬币数量无限制，为完全背包问题。对两问题分别求解，然后找出差额为T时，两者和的最小值即为所示。
FJ身上有各种硬币，但是要买m元的东西，想用最少的硬币个数去买，且找回的硬币数量也是最少（老板会按照最少的量自动找钱），即掏出的硬币和收到的硬币个数最少。
思路：老板会自动找钱，且按最少的找，硬币数量也不限，那么可以用完全背包得出组成每个数目的硬币最少数量。而FJ带的钱是有限的，那么必须用多重背包，因为掏出的钱必须大于m，那么我们所要的是大于等于m钱的硬币个数，但是FJ带的钱可能很多，超过m的很多倍都可能，那么肯定要有个背包容量上限，网上说的根据抽屉原理是m+max*max，这里的max指的是最大面值。而给多了的钱上限是max*max，那么找回的钱也必须是max*max，所以完全背包部分的背包容量是max*max。穷举这max*max个可能就行了。
我的思路：与上面不同的是多重背包的容量应该是m+max，因为如果需要找回的钱大于max，那么老板也只是拿多几张最大面额的给你而已。比如买条烟1329块钱，13+1+1+4=19张RMB， 那么我们可以给他14张，15张，16张，17张，18张100的，老板会相应找回71块，171块，271块，371块，471块，你再往上加钱的话，老板也只是拿更多的100还你，这是多余的。那么最多不会超过一张一百（最大面额）的，也就是1329+100=1429为背包容量。错了很多次！
http://www.cppblog.com/Davidlrzh/articles/135614.htmlint main() 26
{ 27 int N,T,n; 28 int maxV,maxT,minC; 29 30 while(cin>>N>>T) 31 { 32 maxV = 0; 33 for(int i=1; i<=N; i++) 34 { 35 cin>>V[i]; 36 if(maxV < V[i]) //找出最大面值硬币37
{ 38 maxV = V[i]; 39 }40
}41
maxV *= maxV; 42 maxT = T + maxV; //给钱的上界maxT=T+max_Value^243
for(int i=1; i<=N; i++) 44 { 45 cin>>C[i]; 46 }47
48 n = 0; 49 for(int i=1; i<=N; i++) //二进制方法，将多重背包问题转化为01背包问题50
{ 51 for(int j=0; (1<<j)<=C[i]; j++) 52 { 53 ++n; 54 dV[n][1] = 1<<j; 55 dV[n][0] = dV[n][1] * V[i]; 56 }57
if(C[i] > 1) 58 { 59 dV[n][1] = C[i] - dV[n][1] + 1; 60 dV[n][0] = dV[n][1] * V[i]; 61 }62
}63
64 for(int j=0; j<=maxV; j++) //找零dp过程，完全背包65
{ 66 dpC[j] = INF; 67 }68
dpC[0] = 0; 69 for(int i=1; i<=N; i++) 70 { 71 for(int j=V[i]; j<maxV; j++) //从小到大72
{ 73 if(dpC[j] > dpC[j-V[i]] + 1) 74 { 75 dpC[j] = dpC[j-V[i]] + 1; 76 }77
}78
}79
80 for(int j=0; j<=maxT; j++) //给钱dp过程，01背包81
{ 82 dpF[j] = INF; 83 }84
dpF[0] = 0; 85 86 for(int i=1; i<=n; i++) 87 { 88 for(int j=maxT; j>=dV[i][0]; j--) //从大到小89
{ 90 if(dpF[j] > dpF[j-dV[i][0]] + dV[i][1]) 91 { 92 dpF[j] = dpF[j-dV[i][0]] + dV[i][1]; 93 }94
}95
}96
97 minC = INF; 98 for(int j=T; j<=maxT; j++) //两个最小之和为所求99
{100 if(minC > dpF[j] + dpC[j-T])101 {102 minC = dpF[j] + dpC[j-T];103 }104
}105
if(minC != INF)106 {107 cout<<minC<<endl;108 }109
else110
{111 cout<<"-1"<<endl;112 }113
}114
return 0;115}Read full article from 背包问题--POJ 3260 The Fewest Coins【完全背包+多重背包】 - AndreMouche - 博客园
