patterncppMinor

Multiple 0-1 knapsack

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

codereview cpp stackoverflow c++performance knapsack-problem dynamic-programming

knapsackmultiplestackoverflow

Problem

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 
#include 
#include 

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 = 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 > song[i];
    }
    
    int cd[3] = {0,0,0};
    for (int i = 0; i > 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 c

Solution

Prefer to include C++ headers such as `, rather than C compatibility headers (

), 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(-1);


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

#include 
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 songs,
                 std::vector cds)
{
    if (songs.size() > max_songs) { throw std::length_error("songs"); }
    if (cds.size() > max_cds) { throw std::length_error("cds"); }
    std::array 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
#include
#include
#include

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(-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 dpt;

minutes dp(const std::vector& song,
std::array& 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 & songs,
const std::vector& cds)
{
// Argument validation
if (songs.size() > max_songs) {
throw std::length_error("songs");
}
if (std::ranges::max(songs) > max_length) {
throw std::le

Code Snippets

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

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);

#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}));
}

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);
}

#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}));
    E

Context

StackExchange Code Review Q#110050, answer score: 2

Revisions (0)

No revisions yet.