5
\$\begingroup\$

I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs.

Input description

The first input line consists of two positive integers N e K (\$N \le 100\$, \$K \le 3\$), which represent respectively the number of songs and te number of cds. The second input line consists of N positive integers, which represent the duration in minutes of each song. The last input line consists of K positive integers, which represent the maximum number of minutes of music that it is possible to record to each cd. No song has more than 50 minutes, and no cd has available more than 50 minutes of space.

Output description

Print a line containing singly the maximum total number of minutes of music that it is possible to record to the cartridges.

To solve this problem I've programmed a dynamic programming solution where the choices are put the \$i\$th song on each CD or none.

#include <iostream>
#include <algorithm>
#include <string.h>


int dpt[51][51][51][101]; //table for dp

int dp(int *song, int *cd, int n, int k, int element){
    if(element == n)
        return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = 0;

    if(dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] != -1)
        return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element];

    int best = 0;

    for (int i = 0; i < k; ++i) {
        if(cd[i] >= song[element]){
            cd[i] -= song[element];
            best = std::max(best,song[element] + dp(song,cd,n,k,element + 1));
            cd[i] += song[element];
        }
    }

    best = std::max(best,dp(song,cd,n,k,element + 1)); 

    return dpt[ cd[0] ][ cd[1] ][ cd[2] ][element] = best;
}

int main(void){
    int n,k;
    std::cin >> n >> k;

    int song[n];
    for (int i = 0; i < n; ++i) {
        std::cin >> song[i];
    }

    int cd[3] = {0,0,0};
    for (int i = 0; i < k; ++i) {
        std::cin >> cd[i];
    }

    memset(dpt, -1 , sizeof(dpt));
    std::cout << dp(song, cd, n, k, 0) << "\n";
}

This solution takes approximately 1 second with a unknown testbase. But some people got 0 secs. What can I do better here?

Here are some samples:

Input

8 3
7 3 3 2 4 4 2 3
9 8 9

10 1
31 36 16 13 10 13 36 47 1 21
20

10 2
41 8 48 49 33 2 41 26 5 39
22 37

Output

26

17

48
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.