Algotree > Algorithms > Recursive Algorithms 🌀 🌀 🌀 > Finding the value of a dollar sack

Finding the value of a dollar sack

Parent_Sack Problem Statement : Given a large (parent) sack full of dollar coins and smaller sacks within it. Each smaller sack may contain even smaller sacks and dollar coins within it. Objective is to find the total value of the parent sack.

Idea : To find the total value of the parent sack we use a simple recursive algorithm. The algorithm works by going through the contents of the parent sack; if a coin is found in the sack, we add it to the value of the parent sack; if a sack if found we recursively go through its contents to see if we find coins within it to add to the toal value of the sack.

Algorithm : FindSackValue (Object obj)
0.   Initialize total value of the parent sack to 0.
1.   Iterate through the contents of the sack.
       foreach object inside the sack do
2.             if the object is a dollar coin then
                    total_value += value of a dollar coin.
3.             else if the object is a sack (childsack) then
                    total_value += FindSackValue (childsack).
4.             return total_value

Example : In the below image the parent sack contains smaller sacks : S1, S2, S3 and a dollar coin of value $10.
Sack S1 contains dollar coins of value $1, $2 and $3.
Sack S2 contains dollar coins of value $4, $5 and $6.
Sack S3 contains dollar coins of value $7, $8 and a smaller sack S4.
Sack S3 contains dollar coins of value $9.

Directory_Size

C++ : Finding the value of a dollar sack.

#include<iostream>
#include<vector>
#include<map>

using namespace std;

// The class Object represents an object which could either be a Sack or a Coin.

class Object {

    public:
    char type;   // Type of object within the sack could either be a sack (S) or a coin (C)
    string name; // The name / tag of the sack i.e Parent, S1, S2
    int value;   // The value of the coin

    Object (char arg_type, string arg_name, int arg_value) : type(arg_type),
           name(arg_name), value(arg_value)
    { }

    // Instead of writing a Compare class wth operator() overloaded,
    // we can overload < operator in the Object class as below
    /*
    bool operator< (const Object & f) const {
        if (f.name < this->name)
            return true;
    }*/
};

class CompareName {

    public:
    bool operator() (const Object & a, const Object & b) const {
        return (a.name < b.name);
    }
};

class Sack {

    private:

    map<Object, vector<Object>, CompareName> sack_obj;

    public:

    Sack (map<Object, vector<Object>, CompareName> arg_sack) : sack_obj(arg_sack)
    {}

    int FindSackValue (Object obj) {

        int total_value = 0;

        for (const auto& obj : sack_obj[obj]) {

            // If the object found inside the parent sack is a sack, 
            // continue using recursive procedure to find the sack value.
            if (obj.type == 'S') {
                total_value += FindSackValue(obj);
            } else { // If the object is not a sack i.e it is a coin, then add its value
                total_value += obj.value;
            }
        }
        return total_value;
    }
};

int main() {

    map<Object, vector<Object>, CompareName> sack_obj;

    Object parent('S', "Parent", 0);

    Object s1 ('S', "S1", 0);
    Object c1 ('C', "C1", 1);
    Object c2 ('C', "C2", 2);
    Object c3 ('C', "C3", 3);

    Object s2 ('S', "S2", 0);
    Object c4 ('C', "C4", 4);
    Object c5 ('C', "C5", 5);
    Object c6 ('C', "C6", 6);

    Object s3 ('S', "S3", 0);
    Object c7 ('C', "C7", 7);
    Object c8 ('C', "C8", 8);

    Object s4 ('S', "S4", 0);
    Object c9 ('C', "C9", 9);

    Object c10 ('C', "C10", 10);

    // Coin c1, c2 and c3 are inside sack s1
    vector<Object> inside_s1 = { c1, c2, c3 };
    sack_obj.insert ( { s1, inside_s1 } );

    // Coin c4, c5 and c6 are inside sack s2
    vector<Object> inside_s2 = { c4, c5, c6 };
    sack_obj.insert ( { s2, inside_s2 } );

    // Coin c7, c8 and sack s4 are inside sack s3
    vector<Object> inside_s3 = { c7, c8, s4 };
    sack_obj.insert ( { s3, inside_s3 } );

    // Coin c9 is inside sack s4
    vector<Object> inside_s4 = { c9 };
    sack_obj.insert ( { s4, inside_s4 } );

    vector<Object> inside_parent = { s1, s2, s3, c10 };
    sack_obj.insert ( { parent, inside_parent } );

    Sack s(sack_obj);

    cout << "Value of parent sack : " << s.FindSackValue(parent) << endl;
    cout << "Value of sack S1 : " << s.FindSackValue(s1) << endl;
    cout << "Value of sack S2 : " << s.FindSackValue(s2) << endl;
    cout << "Value of sack S3 : " << s.FindSackValue(s3) << endl;
    cout << "Value of sack S4 : " << s.FindSackValue(s4) << endl;

    return 0;
}

Output

Size of root directory : 55
Size of d1 directory : 6
Size of d2 directory : 15
Size of d3 directory : 24
Size of d4 directory : 9