題干：

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?

1 3 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 ; }

?

總結

以上是生活随笔為你收集整理的【qduoj - 142】 多重背包（0-1背包的另类处理，dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。