【qduoj - 142】 多重背包（0-1背包的另类处理，dp）,东芝G900

文件名：【qduoj - 142】 多重背包（0-1背包的另类处理，dp）,东芝G900 【qduoj - 142】 多重背包（0-1背包的另类处理，dp）

题干：

ycb的ACM进阶之路

Description

 

　　ycb是个天资聪颖的孩子，他的梦想是成为世界上最伟大的ACMer。为此，他想拜附近最有威望的dalao为师。dalao为了判断他的资质，给他出了一个难题。dalao把他带到一个到处都是题的oj里对他说：“孩子，这个oj里有一些不同的题，做每一道题都需要一些时间，每一题也有它自身的rp（人品值）。我会给你一段时间，在这段时间里，你可以做一些题。如果你是一个聪明的孩子，你应该可以让做题的总rp最大。” 　　如果你是ycb，你能完成这个任务吗？

Input

输入文件的第一行是一个T，表示测试组数，接下来T组每组第一行包含两个正整数N,M。M表示总共能够用来做题的时间，N代表oj里的题目的数目。接下来的N行每行包括两个的整数，分别表示做每个题的时间Ti和这道题的人品值Vi。 1 <= N, M <= 100000, 1 <= Ti, Vi <= 10

Output

输出文件仅包含一个整数表示规定时间内可以做题得到的最大人品值。

Sample Input 1 

13 9 10 10 8 1 1 2

Sample Output 1

3

Hint

作者：

青岛大学acm集训队1号命题组

Source

lalal

解题报告：

      这题好题啊！！！0-1背包转化成多重背包来做！！因为v和w的数据量都很小 一共100种组合，所以可以枚举然后转化成多重背包来做。

AC代码：

#include<bits/stdc++.h>using namespace std;int n,m;int ji[15][15];int dp[1000000],w[1000000],v[1000000];int main(){int t;int time,rp;cin>>t;while(t--) {scanf("%d%d",&n,&m);memset(ji,0,sizeof(ji));memset(dp,0,sizeof(dp));for(int i =1; i<=n; i++) {scanf("%d%d",&time,&rp);ji[time][rp]++;}int top = 0;for(int i = 1; i<=10; i++) {for(int j = 1; j<=10; j++) {if(ji[i][j] == 0) continue;for(int k = 1; k<=ji[i][j]; k<<=1) {w[++top] = i * k;v[top] = j * k;ji[i][j] -= k;}if(ji[i][j]>0) {w[++top] = ji[i][j] * i;v[top] = ji[i][j] * j;} }}for(int i = 1; i<=top; i++) {for(int j = m; j>=w[i]; j--) {dp[j] = max(dp[j],dp[j - w[i] ] + v[i]);} }printf("%d\n",dp[m]);}return 0 ;}