题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=2639
题目大意：
求第k大背包。
思路：
由01背包递推式dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])，可知，需要求第k大背包的时候状态需要存储前k大，所以设置状态dp[i][j][k]表示前k件物品中体积为j的时候取到的第k大的价值，递推的时候，dp[i][j][1-k]这个序列，需要从dp[i-1][j][1-k]和dp[i-1][j-w[i]][1-k] + v[i]这两个序列中取不重复的前k大构成，注意去重！！（自己序列之间的重复和两个序列之间的重复）
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 #include<algorithm> 5 #include<queue> 6 #include<set> 7 using namespace std; 8 const int maxn = 1e3 + 10; 9 int T, n, m, k; 10 int w[105], v[105]; 11 int dp[maxn][35]; 12 bool cmp(int x, int y) 13 { 14 return x > y; 15 } 16 int main() 17 { 18 scanf("%d", &T); 19 while(T--) 20 { 21 scanf("%d%d%d", &n, &m, &k); 22 for(int i = 0; i < n; i++)scanf("%d", &v[i]); 23 for(int i = 0; i < n; i++)scanf("%d", &w[i]); 24 memset(dp, 0, sizeof(dp)); 25 int a[35], b[35]; 26 for(int i = 0; i < n; i++) 27 { 28 for(int j = m; j >= w[i]; j--) 29 { 30 //dp[i][j][1-k]序列由dp[i-1][j][1-k]和dp[i-1][j-w[i]][1-k]+v[i]两个序列构成 31 for(int c = 1; c <= k; c++) 32 a[c] = dp[j][c], b[c] = dp[j - w[i]][c] + v[i]; 33 int tot = 1, left = 1, right = 1; 34 //for(int i = 1; i <= k; i++)cout<<a[i]<<" "; 35 //for(int i = 1; i <= k; i++)cout<<b[i]<<" "; 36 while(left <= k && right <= k && tot <= k) 37 { 38 if(a[left] > b[right]) 39 { 40 dp[j][tot] = a[left]; 41 while(dp[j][tot] == a[left])left++;//去重，去掉a数组后面重复的元素 42 tot++; 43 } 44 else if(a[left] < b[right]) 45 { 46 dp[j][tot] = b[right]; 47 while(dp[j][tot] == b[right])right++;//去重，去掉b数组后面重复的元素 48 tot++; 49 } 50 else 51 { 52 dp[j][tot] = a[left]; 53 while(dp[j][tot] == a[left])left++;//去重，去掉a和b数组后面重复的元素 54 while(dp[j][tot] == b[right])right++; 55 tot++; 56 } 57 } 58 //此处ab数组可能只走完一个，还需要继续往后遍历 59 while(left <= k && tot <= k)dp[j][tot++] = a[left++]; 60 while(right <= k && tot <= k)dp[j][tot++] = b[right++]; 61 /*for(int i = 1; i <= k; i++) 62 cout<<dp[j][i]<<" "; 63 cout<<endl;*/ 64 } 65 } 66 printf("%d ", dp[m][k]); 67 } 68 return 0; 69 }