Multiple 0-1 knapsack

Question

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 the 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

Answer 1

Prefer to include C++ headers such as <cstring>, rather than C compatibility headers (<string.h>), and adjust the namespaces of their identifiers accordingly. (That said, we don't actually want to use this particular header here - see below).

In C++, every function declaration is a prototype, so we can specify that that it takes no arguments by writing (), unlike C where we must write (void).

We have completely failed to validate our input.

The problem statement's limits are hard-coded throughout. Make them adjustable to enable the code to be re-used.

Avoid using C-style arrays. In C++, we have std::array<> for fixed-size quantities, or std::vector<> for variable-size ones.

Don't write to integer storage as characters. This code only does what you expect by luck (you are probably using a system with two's complement arithmetic):

std::memset(dpt, -1 , sizeof(dpt));

We should use std::fill() to populate containers instead.

The multidimensional vector dpt is obviously essential to the algorithm, but the comment is not at all helpful. What do the indexes and the values mean? Why are the values signed integers?

Since we know that all the numbers we're dealing with (including the total capacity of all CDs) are less than the smallest allowed UCHAR_MAX, we could use unsigned char for our storage and arithmetic, reducing our storage requirement by a factor of sizeof (int).

I suggest

using minutes = unsigned char;

static constexpr std::size_t max_cds = 3;
static constexpr std::size_t max_songs = 100;
static constexpr minutes max_length = 50;
static constexpr minutes max_capacity = 50;

static constexpr minutes unset = static_cast<minutes>(-1);

Really, we'd like to test our function something like this:

#include <gtest/gtest.h>
TEST(Knapsack, NoDisc)
{
    EXPECT_EQ(0, knapsack({}, {}));
    EXPECT_EQ(0, knapsack({1}, {}));
}
TEST(Knapsack, OneDisc)
{
    EXPECT_EQ(0, knapsack({2}, {1}));
    EXPECT_EQ(1, knapsack({1}, {2}));
    EXPECT_EQ(2, knapsack({1, 1}, {2}));
    EXPECT_EQ(1, knapsack({1, 3}, {2}));
    EXPECT_EQ(3, knapsack({2, 3}, {4}));
    EXPECT_EQ(2, knapsack({2, 2, 2, 2, 2}, {3}));
}

To that end, I wrapped the function in a more comfortable C++ interface:

minutes knapsack(std::vector<minutes> songs,
                 std::vector<minutes> cds)
{
    if (songs.size() > max_songs) { throw std::length_error("songs"); }
    if (cds.size() > max_cds) { throw std::length_error("cds"); }
    std::array<minutes, max_cds> cdarr;
    std::ranges::fill(cdarr, 0);
    std::ranges::copy(cds, cdarr.begin());
    std::ranges::fill(dpt, unset);
    return dp(songs.data(), cdarr.data(), songs.size(), cds.size(), 0);
}

Now, let's to the dp() function itself. The signature is very C-like, accepting pointer and length for the collections. We should instead be passing C++ containers (by reference, of course). Although we modify the cds as we go, we should not be modifying the song list, so add a suitable const there.

To be able to use the standard fill algorithm on dpt, I needed to change its type to a linear array. It then became obvious that we repeatedly index into it in several places in the function - rather than repeating code, we should take a reference to the entry.

The last index of dpt goes to 101, but there's really no gain from storing the final zero element, so we can shrink that by a further 1%.

---

Modified code

#include <algorithm>
#include <array>
#include <stdexcept>
#include <vector>

using minutes = unsigned char;

static constexpr std::size_t max_cds = 3;
static constexpr std::size_t max_songs = 100;
static constexpr minutes max_length = 50;
static constexpr minutes max_capacity = 50;

static constexpr minutes unset = static_cast<minutes>(-1);

// Memoization table
// See dp() for indexing arithmetic.
// First three indexes are the three CDs' fill levels.
// Next index is the song size being considered.
// Member at that position is the highest total recorded minutes.
static constexpr auto col_size = max_capacity+1;
static constexpr auto table_size =
    col_size * col_size * col_size * max_songs;
static std::array<minutes, table_size> dpt;

minutes dp(const std::vector<minutes>& song,
           std::array<minutes, max_cds>& cd,
           const std::size_t song_number = 0)
{
    if (song_number == song.size()) {
        // reached end of songs - terminate the recursion
        return 0;
    }

    auto const song_len = song[song_number];
    auto& table_entry =
        dpt[((cd[0] * col_size + cd[1]) * col_size + cd[2]) * col_size
            + song_number];

    if (table_entry == unset) {
        minutes best = 0;
        for (auto& disc: cd) {
            if (disc >= song_len) {
                disc -= song_len;
                minutes candidate = song_len + dp(song, cd, song_number + 1);
                disc += song_len;
                if (best < candidate) { best = candidate; }
            }
        }

        table_entry = std::max(best, dp(song, cd, song_number + 1));
    }

    return table_entry;
}

unsigned int knapsack(const std::vector<minutes>& songs,
                      const std::vector<minutes>& cds)
{
    // Argument validation
    if (songs.size() > max_songs) {
        throw std::length_error("songs");
    }
    if (std::ranges::max(songs) > max_length) {
        throw std::length_error("song length");
    }
    if (cds.size() > max_cds) {
        throw std::length_error("cds");
    }
    if (std::ranges::max(cds) > max_capacity) {
        throw std::length_error("cd capacity");
    }

    std::array<minutes, max_cds> cdarr;
    std::ranges::fill(cdarr, 0);
    std::ranges::copy(cds, cdarr.begin());
    std::ranges::fill(dpt, unset);
    return dp(songs, cdarr);
}

#ifdef SELF_TEST

#include <gtest/gtest.h>
TEST(Knapsack, NoDisc)
{
    EXPECT_EQ(0, knapsack({}, {}));
    EXPECT_EQ(0, knapsack({1}, {}));
}
TEST(Knapsack, OneDisc)
{
    EXPECT_EQ(0, knapsack({2}, {1}));
    EXPECT_EQ(1, knapsack({1}, {2}));
    EXPECT_EQ(2, knapsack({1, 1}, {2}));
    EXPECT_EQ(1, knapsack({1, 3}, {2}));
    EXPECT_EQ(3, knapsack({2, 3}, {4}));
    EXPECT_EQ(2, knapsack({2, 2, 2, 2, 2}, {3}));
}
TEST(Knapsack, TwoDiscs)
{
    EXPECT_EQ(0, knapsack({2}, {1, 1}));
    EXPECT_EQ(2, knapsack({2}, {1, 2}));
    EXPECT_EQ(3, knapsack({2, 1}, {1, 2}));
    EXPECT_EQ(6, knapsack({3, 3, 3}, {5, 3}));
    EXPECT_EQ(7, knapsack({2, 3, 4}, {5, 3}));
    EXPECT_EQ(7, knapsack({2, 2, 3, 2}, {5, 3}));
}

TEST(Knapsack, First_Example)
{
    EXPECT_EQ(26, knapsack({7, 3, 3, 2, 4, 4, 2, 3}, {9, 8, 9}));
}

TEST(Knapsack, Second_Example)
{
    EXPECT_EQ(17, knapsack({31, 36, 16, 13, 10, 13, 36, 47, 1, 21}, {20}));
}

TEST(Knapsack, Third_Example)
{
    EXPECT_EQ(48, knapsack({41, 8, 48, 49, 33, 2, 41, 26, 5, 39}, {22, 37}));
}

#else

#include <iostream>
#include <iterator>

static auto read_vector(std::size_t n)
{
    auto v = std::vector<minutes>{};
    v.reserve(n);
    auto reader = std::istream_iterator<unsigned>(std::cin);
    std::copy_n(reader, n, std::back_inserter(v));
    return v;
}

int main()
{
    for (;;) {
        std::size_t num_songs, num_discs;
        std::cin >> num_songs >> num_discs;
        if (!std::cin) {
            return !std::cin.eof();
        }

        auto const songs = read_vector(num_songs);
        auto const cds = read_vector(num_discs);

        if (!std::cin) {
            return 1;
        }

        std::cout << knapsack(songs, cds) << "\n";
    }
}

#endif

---

We're missing an opportunity to return early if we manage to place all the songs or fill all the CDs. If that happens, there's no need to explore the rest of the search space. This optimisation massively reduces the time taken to run this MaxValues test case:

TEST(Knapsack, MaxValues)
{
    // 50 ✕ 1-minute songs + 50 ✕ 2-minute songs will exactly fill
    // 3 ✕ 50-minute discs
    std::vector<minutes> songs;
    songs.reserve(100);
    std::fill_n(std::back_inserter(songs), 50, 2);
    std::fill_n(std::back_inserter(songs), 50, 1);
    EXPECT_EQ(50, knapsack(songs, {50, 50, 50}));
}

Here's what the code looks like once it's further modified to implement this optimisation:

// Memoization table size
static constexpr auto col_size = max_capacity+1;
static constexpr auto table_size =
    col_size * col_size * col_size * max_songs;

minutes knapsack(const std::vector<minutes>& song,
           std::array<minutes, max_cds>& cd,
           std::array<minutes, table_size>& dpt, // memoization table
           unsigned max_fill,
           const std::size_t song_number = 0)
{
    if (song_number == song.size()) {
        // reached end of songs - terminate the recursion
        return 0;
    }

    auto const song_len = song[song_number];
    auto const next_song = song_number + 1;
    auto const next_max = max_fill - song_len;

    auto& table_entry =
        dpt[((cd[0] * col_size + cd[1]) * col_size + cd[2]) * col_size
            + song_number];

    if (table_entry == unset) {
        minutes best = 0;
        for (auto& disc: cd) {
            if (disc >= song_len) {
                disc -= song_len;
                minutes candidate = song_len + knapsack(song, cd, dpt,
                                                        next_max, next_song);
                disc += song_len;
                if (candidate == max_fill) {
                    // perfect result
                    return candidate;
                }
                if (best < candidate) { best = candidate; }
            }
        }

        table_entry = std::max(knapsack(song, cd, dpt, next_max, next_song),
                               best);
    }

    return table_entry;
}

unsigned int knapsack(const std::vector<minutes>& songs,
                      const std::vector<minutes>& cds)
{
    // Memoization table
    // See knapsack() for indexing arithmetic.
    // First three indexes are the three CDs' remaining capacity.
    // Next index is how many songs have already been packed or discarded.
    // Member at that position is the highest total recorded minutes.
    static std::array<minutes, table_size> memoization;

    // Argument validation
    if (songs.empty() || cds.empty()) {
        return 0;
    }
    if (songs.size() > max_songs) {
        throw std::length_error("songs");
    }
    if (std::ranges::max(songs) > max_length) {
        throw std::length_error("song length");
    }
    if (cds.size() > max_cds) {
        throw std::length_error("cds");
    }
    if (std::ranges::max(cds) > max_capacity) {
        throw std::length_error("cd capacity");
    }

    auto const max_fill = std::min(std::accumulate(cds.begin(), cds.end(), 0u),
                                   std::accumulate(songs.begin(), songs.end(), 0u));
    std::array<minutes, max_cds> cdarr;
    std::ranges::fill(cdarr, 0);
    std::ranges::copy(cds, cdarr.begin());
    std::ranges::fill(memoization, unset);
    return knapsack(songs, cdarr, memoization, max_fill);
}

---

Beyond this, the most time-consuming test is this one:

TEST(Knapsack, AlmostFull)
{
    // 100 ✕ 2-minute songs will fill 2 ✕ 50-minute discs
    // and not quite fill a 49-minute disc
    std::vector<minutes> songs(100, 2);
    EXPECT_EQ(148, knapsack(songs, {50, 50, 49}));
}

Although all the 2-minute songs are interchangeable, we spend a lot of time considering whether to exclude combinations of them. To speed up this test, we'll have to change our data structure to gather the candidates in some kind of Bag. At this point, the simple memoization storage won't work any more, and we'll need to use a more complex structure such as an unordered map from a state structure to fill-level.