UVa 473

base on traditional 0/1 knapsack dp, here we have multiple knapsacks therefore DP matrix turns to 3 dimensions
the 3rd transformation is what makes this different from traditional 0/1 knapsack dp
state:
     dp[i][j][k] - iterates songs with i while k minutes left in disk j
transformation:
    if k>=s[i], means can add song i
        dp[i+1][j][k]=max(dp[i][j][k], dp[i][j][k-s[i]]+1)
    or k<s[i], means no more song can be added to disk j
        dp[i+1][j][k]=dp[i][j][k]
    fall through, we check if more songs can be added to a new disk if j>0, means there are still other disks to use
        dp[i+1][j][k]=max(dp[i+1][j][k], dp[i][j-1][t-s[i]]+1)

/* UVas */
/*****************************************************************************/
int c, n, t, m, tmp;
int d[800][100][100];
int s[800];
int main(void) {
    cin>>c;
    while (c--) {
        cin>>n>>t>>m;
        int p=0;
        scanf("%d", s+p++);
        for (int i=1; i<n; i++) {
            scanf(", %d", s+p++);
        }
        memset(d, 0, sizeof(d));
        for (int i=0; i<n; i++) {
            for (int j=0; j<=m; j++) {
                for (int k=0; k<=t; k++) {
                    if (k<s[i]) {
                        d[i+1][j][k]=d[i][j][k];
                    } else {
                        d[i+1][j][k]=max(d[i][j][k], d[i][j][k-s[i]]+1);
                    }
                    if (j>0) {
                        d[i+1][j][k]=max(d[i+1][j][k], d[i][j-1][t-s[i]]+1);
                    }
                }
            }
        }
        int r=0;
        for (int i=0; i<=n; i++) {
            r=max(r, d[i][m][0]);
        }
        cout<<r<<endl;
        if (c) {
            cout<<endl;
        }
    }
    return 0;
}
/*****************************************************************************/