HiHoCoder_offer6_04
题目4 : 奖券兑换
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi在游乐园中获得了M张奖券，这些奖券可以用来兑换奖品。
可供兑换的奖品一共有N件。第i件奖品需要Wi张奖券才能兑换到，其价值是Pi。
小Hi使用不超过M张奖券所能兑换到的最大奖品总价值是多少？
输入
第一行两个整数N，M。
接下来N行，每行两个整数Wi，Pi。
对于 50%的数据： 1≤N,M≤1000
对于 100%的数据： 1≤N,M≤105,1≤Pi,Wi≤10。
输出
一行一个整数，表示最大的价值。
- 样例输入
-
3 10 2 3 8 8 10 10
样例输出 -
11
明显是一个01背包问题，背了一下结果：过了一半的数据，剩下的TLE了。 仔细观察数据， 1 <= n , m <= 100000, 1 <= wi , pi <= 10。明显每个物品的价值和容量都非常小，也就是说不同容量不同不价值的物品最多有：10 * 10 = 100种。
既然这个数据项这么小，那么它就是这个问题的突破口。对于每一个物品，已知它的num(数量 )和 weight(重量) & value(价值),刚好可以使用多重背包。加上二进制优化，复杂度O(10 * 10 * log 100000);
代码：
#include#include #include using namespace std;int num[15][15];int dp[100005];void CompletePack(int weight, int value, int totWeight){ for(int w = weight; w <= totWeight; w ++){ dp[w] = max(dp[w], dp[w - weight] + value); }}void zeroOnePack(int weight, int value, int totWeight){ for(int w = totWeight; w >= weight; w --){ dp[w] = max(dp[w], dp[w - weight] + value); }}void multiPack(int weight, int value, int totWeight){ if(weight * num[weight][value] > totWeight){ CompletePack(weight, value, totWeight); }else{ int k = 1, tmpNum = num[weight][value]; while(k < tmpNum){ zeroOnePack(k * weight, k * value, totWeight); tmpNum -= k; k <<= 1; } zeroOnePack(tmpNum * weight, tmpNum * value, totWeight); }}int main(){ int n,m,weight,value; cin>>n>>m; for(int i = 0; i < n; i ++){ scanf("%d%d",&weight, &value); num[weight][value] ++; } for(int i = 1; i <= 10; i ++){ for(int j = 1; j <= 10; j ++){ multiPack(i, j, m); } } printf("%d\n",dp[m]); return 0;}
————————++++++————————