01背包（求前一个的最大价值-->求前K个的最大价值） 之 hdu 2639

//  [7/21/2014 Sjm]
/*
此题我想的思路错了，情况考虑漏了。。。
解法是由 求前一个的最大价值-->求前K个的最大价值 的转化。

求前一个最大价值：      
　　dp[i][j] = max(dp[i-1][j], dp[i-1][j-C[i]] + W[i])
求前K个的最大价值      
　　同样，dp[i][j]的前 k 个最大价值，是依赖于 dp[i-1][j] 的前 k 个最大价值和 dp[i-1][j-C[i]] 的前 k 个最大价值所求得的。      
　　由此考虑了所有情况，求出了答案。

*/

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 100005;
const int MAX_N = 105;
const int MAX_K = 35;
int N, V, K;
int arr[MAX_N][2], dp[MAX][MAX_K];
int tep1[MAX_K], tep2[MAX_K];

int Solve() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= N; ++i) {
        for (int j = V; j >= arr[i][1]; --j) { 
            for (int k = 1; k <= K; ++k) {
                // 注意：经过此循环，tep1[], tep2[]均是递减排列的。（根据01背包的原理）
                tep1[k] = dp[j - arr[i][1]][k] + arr[i][0];
                tep2[k] = dp[j][k];
            }
            tep1[K + 1] = tep2[K + 1] = -1;
            int pos1 = 1, pos2 = 1;
            for (int k = 1; (pos1 <= K || pos2 <= K)&&k <= K;) {
                if (tep1[pos1] > tep2[pos2]) { dp[j][k] = tep1[pos1++]; }
                else { dp[j][k] = tep2[pos2++]; }
                if (dp[j][k] != dp[j][k - 1]) {
                    ++k;
                }
            }
        }
    }
    return dp[V][K];
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &N, &V, &K);
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &arr[i][0]);
        }
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &arr[i][1]);
        }
        printf("%d
", Solve());
    }
    return 0;
}