1
\$\begingroup\$

The assignment is to be implemented on the following instructions:

You are to write a Knapsack class and the main() to support and demonstrate the functionality required here.

A function generate(int) is prototyped in collect.h and defined in the library libGenerate.a. It returns a letter (char) that identifies which object you need to try and fit into your knapsack. You need to pass an object of that type to the knapsack using a function template/template function defined inside Knapsack. That function template should take an object of arbitrary type and attempt to ”add it” to the knapsack. If the object fits, based on the size using sizeof, you record that object as being included, using the name attribute of the classes. The object itself should not be stored in the knapsack. Once the next object to be passed cannot be added to the knapsack, you should stop generating objects.

More details:

Private members in the Knapsack class are:

size : A positive integer. The size of the knapsack.

seed : A positive integer. Random seed to be passed to the generate function.

the generate function is prototyped and a c++ library .a file is included as well. (This works)

Header file required for assignment:

#ifndef COLLECT_H
#define COLLECT_H

char generate(int seed);

class A  // size --> 1 {
private:
    char name;

public:
    A(){name='A';}
    char getName(){return name;}
};

class B  // size --> 2 {
private:
    char name;
    char B1;

public:
    B(){name='B';}
    char getName(){return name;}
};

class C // size --> 4 {
private:
    char name;
    char C1,C2,C3;

public:
    C(){name='C';}
    char getName(){return name;}
};

class D // size --> 8 {
private:
    char name;
    char D1,D2,D3;
    int D4;

public:
    D(){name='D';}
    char getName(){return name;}
};

class E  // size --> 16 {
private:
    char name;
    char E1,E2,E3;
    int E4, E5, E6;

public:
    E(){name='E';}
    char getName(){return name;}
};

class F // size --> 32 {
private:
    char name;
    char F1,F2,F3;
    int F4, F5, F6;
    double F7, F8;

public:
    F(){name='F';}
    char getName(){return name;}
};

class G  // size --> 64 {
private:
    char name;
    char G1,G2,G3;
    int G4,G5,G6;
    double G7,G8;
    long double G9,G10;

public:
    G(){name='G';}
    char getName(){return name;}
};

#endif

Full code:

#include <iostream>
#include <string>
#include <vector>
#include "collect.h" // no need to submit this

template <class T>
class Knapsack
{
    private: 
      int size;
      int seed; 
      T obj;
    public:
      Knapsack(int, int);
      int getsize();
      int addtoknapsack(T obj);
};

template <class T>
Knapsack<T>::Knapsack(int _size, int _seed): size(_size), seed(_seed) {}

template <class T>
int Knapsack<T>::getsize()
{
    return size;
}

template <class T>
int Knapsack<T>::addtoknapsack(T obj)
{
    int objsize = sizeof(obj);
    if(size > objsize)
    {
        size -= sizeof(obj);
        // std::cout << size << std::endl;
        return size;
    }
    else
    {
        return size;
    }

}


int main(int argc, char *argv[])
{
    int knapsacksize = strtol(argv[1], nullptr, 0);
    int seed = strtol(argv[2], nullptr, 0);
    int objsize = 0;

    // set capacity, will not be changed
    int capacity = knapsacksize;

    std::vector<char> objlist;

    std::cout << "===========================" << std::endl;
    std::cout << "== C++ Knapsack problem ===" << std::endl;
    std::cout << "============== ~Gh0u1Ss ===" << std::endl;

    std::cout << "Knapsack Size: " << knapsacksize << std::endl;

    Knapsack<int> thisknapsack(knapsacksize,seed);

    // knapsacksize with decrease as objects are being added
    while(knapsacksize > objsize)
    {
        char cresult = generate(seed);

        //std::cout << knapsacksize << std::endl;

        if (cresult == 'A')
        {
            A a;
            // compare objsize with knapsacksize decreasing every interation to break the loops
            // knapsacksize decreases and stops adding objects when objsize is greater than knapsacksize
            objsize = sizeof(a); 
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
                Knapsack<A> thisknapsack(knapsacksize,seed);
                knapsacksize = thisknapsack.addtoknapsack(a); // knapsacksize decreases here
                objlist.push_back(a.getName());  // using getname: is this acceptable?
            }
        }
        else if(cresult == 'B')
        {
            B b;
            objsize = sizeof(b);
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
               Knapsack<B> thisknapsack(knapsacksize,seed);
               knapsacksize = thisknapsack.addtoknapsack(b);
               objlist.push_back(b.getName());
            }
        }
        else if(cresult == 'C')
        {
            C c;
            objsize = sizeof(c);
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
                Knapsack<C> thisknapsack(knapsacksize,seed);
                knapsacksize = thisknapsack.addtoknapsack(c);
                objlist.push_back(c.getName());
            }
        }
        else if(cresult == 'D')
        {
            D d;
            objsize = sizeof(d);
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
                Knapsack<D> thisknapsack(knapsacksize,seed);
                knapsacksize = thisknapsack.addtoknapsack(d);
                objlist.push_back(d.getName());
            }
        } 
        else if(cresult == 'E')
        {
            E e;
            objsize = sizeof(e);
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
                Knapsack<E> thisknapsack(knapsacksize,seed);
                knapsacksize = thisknapsack.addtoknapsack(e);
                objlist.push_back(e.getName());
            }
        }
        else if(cresult == 'F')
        {
            F f;
            objsize = sizeof(f);
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
                Knapsack<F> thisknapsack(knapsacksize,seed);
                knapsacksize = thisknapsack.addtoknapsack(f);
                objlist.push_back(f.getName());
            }
        }
        else if(cresult == 'G')
        {
            G g;
            objsize = sizeof(g);
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
                Knapsack<G> thisknapsack(knapsacksize,seed);
                knapsacksize = thisknapsack.addtoknapsack(g);
                objlist.push_back(g.getName());
            }
        }   
        
        objsize = 0; // Bug log: refresh objsize to compare with next object size on next iteration
         
        //objlist.push_back(cresult);
    }

    int addedobjsize = capacity - knapsacksize;

    std::cout << "Knapsack Size: " << addedobjsize << std::endl;

    for (char character : objlist)
    {
        std::cout << character;
    }

    int countA = 0;
    int countB = 0;
    int countC = 0;
    int countD = 0;
    int countE = 0;
    int countF = 0;
    int countG = 0;

    std::cout << std::endl;

    for (char character : objlist)
    {
        if(character == 'A')
        {
           countA++;
        }
        else if(character == 'B')
        {
           countB++;
        }
        else if(character == 'C')
        {
           countC++;
        }
        else if(character == 'D')
        {
           countD++;
        }
        else if(character == 'E')
        {
           countE++;
        }
        else if(character == 'F')
        {
           countF++;
        }
        else if(character == 'G')
        {
           countG++;
        }
    }

    if(countA > 0)
    {
        std::cout << "A : 1, " << countA << std::endl; 
    }
    if(countB > 0)
    {
        std::cout << "B : 2, " << countB << std::endl; 
    }
    if(countC > 0)
    {
        std::cout << "C : 4, " << countC << std::endl; 
    }
    if(countD > 0)
    {
        std::cout << "D : 8, " << countD << std::endl; 
    }
    if(countE > 0)
    {
        std::cout << "E : 16, " << countE << std::endl; 
    }
    if(countF > 0)
    {
        std::cout << "F : 32, " << countF << std::endl; 
    }
    if(countG > 0)
    {
        std::cout << "G : 64, " << countG << std::endl; 
    }
      
    return 0;
}

Refer to the template function and while loop in main() method:

Even though my program complies and runs successfully, I feel that my program logic design is bad (when working in industry) because the condition to check if the knapsack can fit more items is being checked two times:

Note: items have different sizes (classes in c++, see the header file)

In the addtoknapsack() function --> if(size > objsize)

In the main() function --> while(knapsacksize > objsize)

How can I improve on it such that the condition is only checked once? (Preferably in addtoknapsack() function)

Output:

Knapsack Size: 180
Knapsack Size: 177
CBDFBGAFF
A : 1, 1
B : 2, 2
C : 4, 1
D : 8, 1
F : 32, 3
G : 64, 1
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ Oct 21, 2022 at 14:32

1 Answer 1

2
\$\begingroup\$

There are a lot of problems with the code, but before I even start with that, I have to point out that I think you failed to understand the problem given.

This is what the problem description says:

You are to write a Knapsack class ...

... You need to pass an object of that type to the knapsack using a function template/template function defined inside Knapsack. That function template should take an object of arbitrary type and attempt to ”add it” to the knapsack. ...

What you were asked to do is create a class with a function template. What you did was create a class template with a function (that is not a template). In other words:

// This is a class template...
template <typename T>
class knapsack
{
    // ... with a non-template function.
    auto add(T);
};

// This is a (non-template) class...
class knapsack
{
    // ... with a function template.
    template <typename T>
    auto add(T);
};

It’s partly because you got that wrong that you have ended up with code that is mostly absurd, with insane amounts of duplication and lots of dead-ends and pointless complexity.

You see, because you have templated the knapsack (and not the add function), you have been forced to create dozens and dozens of knapsacks in your code. You just keep creating them, and then throwing them away:

    std::cout << "===========================" << std::endl;
    std::cout << "== C++ Knapsack problem ===" << std::endl;
    std::cout << "============== ~Gh0u1Ss ===" << std::endl;

    std::cout << "Knapsack Size: " << knapsacksize << std::endl;

    /*******************************************************************
     * This knapsack is created, and then just... thrown away.
     * It's never used again.
     * And, bizarrely, it's created with a template parameter of int.
     * That just makes no sense at all. What does int have to do with
     * anything? I know you just needed something to make it work...
     * but "slap anything in there to make it work" is literally the
     * opposite of good programming.
     ******************************************************************/
    Knapsack<int> thisknapsack(knapsacksize,seed);

    // knapsacksize with decrease as objects are being added
    while(knapsacksize > objsize)
    {
        char cresult = generate(seed);

        //std::cout << knapsacksize << std::endl;

        if (cresult == 'A')
        {
            A a;
            // compare objsize with knapsacksize decreasing every interation to break the loops
            // knapsacksize decreases and stops adding objects when objsize is greater than knapsacksize
            objsize = sizeof(a); 
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
                /*******************************************************
                 * This knapsack is created for no other reason than to
                 * do `knapsacksize += sizeof(A);`...
                 ******************************************************/
                Knapsack<A> thisknapsack(knapsacksize,seed);
                knapsacksize = thisknapsack.addtoknapsack(a); // knapsacksize decreases here
                objlist.push_back(a.getName());  // using getname: is this acceptable?
                /*******************************************************
                 * ... and it's immediately destroyed here.
                 ******************************************************/
            }
        }
        else if(cresult == 'B')
        {
            B b;
            objsize = sizeof(b);
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
               /********************************************************
                * AGAIN, a knapsack is created for no other reason than
                * to do `knapsacksize += sizeof(B);`...
                *******************************************************/
               Knapsack<B> thisknapsack(knapsacksize,seed);
               knapsacksize = thisknapsack.addtoknapsack(b);
               objlist.push_back(b.getName());
               /********************************************************
                * ... and AGAIN it's immediately destroyed here.
                *******************************************************/
            }
        }
        /***************************************************************
         * And the same thing happens again and again, for every type:
         * pointless knapsacks are created, then discarded.
         **************************************************************/

If you think about it for a second, that just makes no sense. You’re supposed to have ONE knapsack… not dozens of them. And if you’re putting things in and expecting to query the contents later, it makes no sense to be throwing the knapsack(s) away over and over.

And this is really the problem throughout the code. Rather than taking the time to THINK about what you need and what should be happening, you’re just blindly throwing everything at the wall to see what sticks. This is not programming, this is just hacking.

I would advise throwing the whole thing out and starting from scratch. First, make a proper knapsack class. THINK it through: what does the knapsack class need? It needs to know its total size, and it needs to keep track of its contents and their size. Your current knapsack class knows its total size—that’s good—but then it knows a random seed it never uses—why?—and it only holds a single object.

Once you get the knapsack class right, you will avoid any need for the rest of the absurdity in your code, like the fact that you have a knapsack class, yet you’re keeping track of the objects in the knapsack using a separate vector (objlist). Isn’t that weird? When you put things in a bag, do you actually put nothing in that bag, but rather have a separate thing keeping track of what’s supposed to be in that bag? That’s not how bags work.

The bottom line is that you need to completely rethink what your code is doing, or rather, perhaps, think it through for the first time. C++ is a modelling language, so THINK about what you are modelling: what are the “objects”, what are their properties, how do they interact, and so on. Once you do that, everything will just fall together, and silliness like double-checking the fit condition won’t be a problem anymore.

Code review

I’m not sure whether the header is supposed to be part of the review, but, meh, it’s terrible anyway, so maybe at least someone can learn from having it reviewed.

char generate(int seed);

Without seeing the body of the function, there’s no way to know how it actually works, but repeatedly reseeding a pseudo-random generator is generally a bad idea. A proper interface would have a separate seed function and generate function. (As with std::srand() and std::rand(), but don’t use those, they are garbage.)

class A  // size --> 1 {
private:
    char name;

public:
    A(){name='A';}
    char getName(){return name;}
};

class B  // size --> 2 {
// ... [snip] ...

class C // size --> 4 {
// ... [snip] ...

// ... [etc.] ...

Hoo boy.

Okay, first of all, this code assumes that sizeof(int) is 4, not to mention assumptions about the size of double and long double. Maybe, maybe not. Even if it “works” on your platform, it makes no sense when there are easier and better ways to guarantee a size of 4, portably. More or less.

You see, there is technically no way to guarantee a size of anything. The C++ compiler is free to add padding as it pleases. But let’s ignore that complication for now. (For the record, you can fix that with compiler switches and pragmas. But that’s compiler-specific stuff.)

So all you want is a set of types of a fixed size. No problem:

template <char Name, int Size>
    requires (Size >= 1)
class fixed_size_type
{
    char _data[Size];

public:
    // Could also make this constexpr and noexcept:
    auto getName() const { return Name; }
};

using A = fixed_size_type<'A', 1>;
using B = fixed_size_type<'B', 2>;
using C = fixed_size_type<'C', 4>;
// ... and so on ...

“Don’t Repeat Yourself (DRY)” is a core rule of good programming.

I would also recommend against using .h as the extension for C++ header files. That is the C header file extension. Unless your header is intended to be compatible with C, you should use .hpp or .hxx or something else to clearly mark it as a C++ header file.

Okay, onto the main source file.

template <class T>
class Knapsack
{
    private: 
      int size;
      int seed; 
      T obj;
    public:
      Knapsack(int, int);
      int getsize();
      int addtoknapsack(T obj);
};

So I’ve already explained why this class is all wrong, and needs to be rewritten. I’m not going to spell out exactly how to rewrite it, because I suspect that’s the point of the lesson. I will, however, give some tips.

All your knapsack class needs to know is its total size, the list of objects it contains, and their total size. For the list of objects, you could just use that objlist vector<char> that is currently external to the knapsack as a data member. All the class needs to do is report its total size, its current size and the list of objects it contains, and have a function to add new objects. The add function should check that the new object will fit, and return an error (or throw an exception) if not. All you need to do in main() is keep adding objects until you get that error. Simple.

    int knapsacksize = strtol(argv[1], nullptr, 0);
    int seed = strtol(argv[2], nullptr, 0);

There is no error-checking done here. Since this is just a toy program, that’s probably fine, but obviously you shouldn’t do this in a real program.

    int objsize = 0;

There is no point creating this variable here. It’s not used until a couple dozen or so lines later.

    // set capacity, will not be changed
    int capacity = knapsacksize;

The word for “will not be changed” in C++ is const.

    std::vector<char> objlist;

As already mentioned, the knapsack should be keeping track of the objects it contains. There should be no need for an external variable.

    std::cout << "===========================" << std::endl;
    std::cout << "== C++ Knapsack problem ===" << std::endl;
    std::cout << "============== ~Gh0u1Ss ===" << std::endl;

Don’t use std::endl. It’s (almost) always wrong. If you want a new line, just write a new line: "\n" or '\n'. It’s not only going to be significantly faster, it’s also shorter to write.

By the by, there is no need to split this message over 6 different output operations. You could just do:

    std::cout << "===========================\n"
                 "== C++ Knapsack problem ===\n"
                 "============== ~Gh0u1Ss ===\n";

The strings will be automatically merged.

    std::cout << "Knapsack Size: " << knapsacksize << std::endl;

Given how many variables you have floating around keeping track of one size or another, you should be more careful with terminology. I believe what you mean to specify here is the knapsack capacity.

And knapsacksize probably means remaining capacity, but your logic is so confused it’s hard to tell.

    Knapsack<int> thisknapsack(knapsacksize,seed);

This knapsack object is created and… just never used. It’s also instantiated with an int template parameter, which means… nothing. It’s just gibberish.

    // knapsacksize with decrease as objects are being added
    while(knapsacksize > objsize)

Why are you testing this here? There are no objects yet (on the first run through), so this test is nonsense. objsize shouldn’t even exist yet, because you don’t have any objects to have a size of.

    // knapsacksize with decrease as objects are being added
    while(knapsacksize > objsize)
    {
        char cresult = generate(seed);

        //std::cout << knapsacksize << std::endl;

        if (cresult == 'A')
        {
            A a;
            // compare objsize with knapsacksize decreasing every interation to break the loops
            // knapsacksize decreases and stops adding objects when objsize is greater than knapsacksize
            objsize = sizeof(a); 
            if (objsize > knapsacksize)
            {
                break;
            }
            else
            {
                Knapsack<A> thisknapsack(knapsacksize,seed);
                knapsacksize = thisknapsack.addtoknapsack(a); // knapsacksize decreases here
                objlist.push_back(a.getName());  // using getname: is this acceptable?
            }
        }
        else if(cresult == 'B')
        {

        // ... [snip repeated blocks] ...

Okay, this is the meat of the main() function, and it’s basically just the same if block repeated over and over. Whenever you see repetition like this, it’s a signal that you need to create a function.

Every if block looks like this:

if (cresult == 'T')
{
    T t;
    objsize = sizeof(t); 
    if (objsize > knapsacksize)
    {
        break;
    }
    else
    {
        Knapsack<T> thisknapsack(knapsacksize,seed);
        knapsacksize = thisknapsack.addtoknapsack(t);
        objlist.push_back(t.getName());
    }
}

… where T/t gets replaced with “A” through “G”.

First, let’s simplify by removing some of the unnecessary garbage. If you had a proper knapsack class with a proper add function—one that returns false if the new object won’t fit—then this block becomes this:

if (cresult == 'T')
{
    if (not knapsack.add(T{}))
        break;
}

Amazing, right? That’s what it looks like when you get the types right.

So let’s pull all those if blocks out and put them in a function:

auto add_to_knapsack(knapsack& knap, char item)
{
    switch (item)
    {
    case 'A':
        if (not knapsack.add(A{}))
            return false;
        break;
    case 'B':
        if (not knapsack.add(B{}))
            return false;
        break;
    // ... [and so on] ...
    }

    return true;
}

Now the loop in main() is just:

while (add_to_knapsack(knap, generate(seed)))
{
    // This block is empty.
}

That’s literally it. That’s pretty much the whole program. That’s over a hundred lines of code gone. and it’s maximally efficient: no repeated tests or any other nonsense.

Finally, there’s the histogram calculation at the end. Once again, there’s a crap ton of duplicated code. But all you need is a single map:

auto counts = std::map<char, int>{};

// This does all the counting.
for (auto character : objlist)
    ++counts[character];

// This does all the printing.
for (auto [character, count] : counts)
    std::cout << character << " : " << get_object_size_by_name(character) << ", " << count << "\n";

// Notice the get_object_size_by_name() function in there. All that does
// is take the character, figure out which type it represents, and then
// return the size, like so:
auto get_object_size_by_name(char name)
{
    switch (name)
    {
    case 'A': return sizeof(A);
    case 'B': return sizeof(B);
    // ... [ and so on ] ...
    }

    // Handle errors here.
}

Everything starts with getting the types right, though. Because you got the knapsack class wrong, everything turned into a disaster. If you got the knapsack type right, everything would flow smoothly, you would get simpler and clearer code, and there would be no inefficiencies or duplication.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.