Tried to solve problem given in https://stackoverflow.com/questions/53939655/generating-in-order-constrained-sets

main.cpp

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <queue>
#include <time.h>
#include <bitset>
#include <algorithm>
#include <functional>

using namespace std;

int TC = 5;
int MAX_CATEGORY = 32;
int MIN_ITEMS = 1000;
int MAX_ITEMS = 1000;
int MAX_PRICE = 10;
int MIN_PRICE = 2;
int MAX_RAND_VALUE = 100;
int MAX_ITEM_ID = 10000;
int PRICE_TAG = 50;
int TOP_X = 100;

class Item {
public:
    // using single unsigned int bitwise check sets
    unsigned int category;
    int name;
    int value;
    int price;

    Item(unsigned int c, int i, int v, int p) : category(c), name(i), value(v), price(p) {}

    void print() {
        cout << "name=" << name << " value=" << value << " price=" << price << " category=";
        int i = 0;
        while (category) {
            if (category & 1) {
                cout << i << ",";
            }
            category = category >> 1;
            i++;
        }
        cout << endl;
    }

    friend bool operator== (const Item &n1, const Item &n2);
};

class ItemSet
{
public:
    set<Item> items;
    int sum;
};

bool operator== (const Item& item1, const Item& item2)
{
    return (item1.category == item2.category) && 
        (item1.name == item2.name) &&
        (item1.price == item2.price) &&
        (item1.value == item2.value);
}

bool operator<(const ItemSet& item1, const ItemSet& item2) {
    return item1.sum < item2.sum;
}

bool operator<(const Item& item1, const Item& item2) {
    if (item1.value == item2.value) {
        if (item1.price == item2.price) {
            return item1.name < item2.name;
        }
        return item1.price > item2.price;
    }
    return item1.value < item2.value;
}

bool operator>(const Item& item1, const Item& item2) {
    if (item1.value == item2.value) {
        return item1.price < item2.price;
        if (item1.price == item2.price) {
            return item1.name > item2.name;
        }
    }
    return item1.value > item2.value;
}

priority_queue<ItemSet> output;

vector<Item> generateTestItem()
{
    int items = MIN_ITEMS+rand() % MAX_ITEMS; // amount of items
    srand(time(NULL));
    vector<Item> v;
    set<int> itemDuplicateTester;
    for (int j = 0; j < items; ++j) {
        int catSize = rand() % 10; // amount of categories for each item
        unsigned int cats = 0;
        for (int c = 0; c <= catSize; ++c) {
            int r = rand() % MAX_CATEGORY;
            cats |= 1 << r;
        }
        int itemId = rand() % MAX_ITEM_ID;
        int value = rand() % MAX_RAND_VALUE;
        int price = MIN_PRICE + rand() % MAX_PRICE;
        // make sure generated item is unique with itemDuplicateTester
        if (itemDuplicateTester.find(itemId) == itemDuplicateTester.end()) {
            v.push_back(Item(cats, itemId, value, price));
            itemDuplicateTester.insert(itemId);
            //v.back().print();
        }
    }
    return v;
}

void addOutput(set<Item>& currentItems)
{
    ItemSet myset;
    int setsum = 0;
    for (auto a : currentItems) {
        setsum += a.value;
    }
    myset.items = currentItems;
    myset.sum = setsum;
    output.push(myset);
}

void helper(vector<Item>& input, set<Item>& currentItems, unsigned int currentCats, int sum, int index)
{
    if (index == input.size()) {
        // Need to check if currentItems matches the blueprint
        // if yes, then call addOutput
        addOutput(currentItems);
        return;
    }
    if (output.size() >= TOP_X) {
        return;
    }
    if (sum + input[index].price < PRICE_TAG) {
        // this condition needs to be changed
        // we need to have category checker method which would return true if we are ok to include 
        // input[index] item's category as per blueprint
        if ((input[index].category & currentCats) == 0) {
            currentItems.insert(input[index]);
            helper(input, currentItems, currentCats | input[index].category, sum + input[index].price, index + 1);
        }
    } else {
        // Need to check if currentItems matches the blueprint
        // if yes, then call addOutput
        addOutput(currentItems);
        return;
    }
    if (currentItems.find(input[index]) != currentItems.end()) {
        currentItems.erase(input[index]);
    }
    helper(input, currentItems, currentCats, sum, index + 1);
    return;
}

void getTopItems(vector<Item>& items)
{
    set<Item> myset;
    helper(items, myset, 0, 0, 0);
}

int main()
{
    for (int i = 0; i < TC; ++i) {
        vector<Item> v = generateTestItem();
        cout << "generated items : " << v.size() << endl;
        sort(v.begin(), v.end(), greater<Item>());
        getTopItems(v);
        cout << "got ans " << output.size() << endl;
        int j = 0;
        while (output.empty() == false) {
            set<Item> myset = output.top().items;
            output.pop();
            int priceSum = 0, valueSum = 0;
            for (auto a : myset) {
                priceSum += a.price;
                valueSum += a.value;
            }
            j++;
            cout << "set size=" << myset.size() <<  " priceSum= " << priceSum << "  valueSum = " << valueSum << endl;
        }
    }
    return 0;
}

I can't simply choose the next best one, because it could very well be that as I choose the best values to fit in my set, the price of those items can only leave a very small valued item whose price is also low, however the value can be so small of this last item, that it may be better to equalize over lower valued items but overall they have higher values when fitted into the set.

Using a straightforward 'get the next best' type of algorithm will not be able to encounter this specific case where in total average items will accumulate to a better set because they are able to fit in this constrained categorized set.
However using this type of algorithm can still be beneficial to still get a reasonable high value set, but it's not optimal.

If I wasn't clear enough I have an example by paper I can make a video or draw on a white board and share with you.

Tell me if you understand my point and if you have a solution because I broke my head on this for a while.

I think I can understand you, though having some real examples would help more.

Do you think if we change input items so that they have only single category, we can achieve our goal easier? For ex if cheese has 2 cats: Food and Diary, we can separate it and have 2 cheeses, one with cat food and one with cat diary. When we build up our output sets, we make sure that items with same names does not go inside single set. And, of course, we will be following blueprint for output.

I will make a video showing why simple descent on a sorted list isn't optimal. In respect to your question, I have delved in this problem for a while now and haven't found that this should be necessary at all. We could simply use an unordered set and check for duplicates, which is O(1) time. There are many efficient ways to deal with duplicate items, the harder problem is how to efficently make sure that duplicate sets aren't generated which can happen if we have categories that share other categories, like Food and Cheese. I am so close to a dynamic solution and it consequentially takes care of duplicate sets due to the nature of the algorithm. But if you have any insight please by all means let me know. Hope to post a video depicting an example soon, thanks!

…

On Fri, Jun 28, 2019, 1:14 AM Miradham Kamilov ***@***.***> wrote: I think I can understand you, though having some real examples would help more. Do you think if we change input items so that they have only single category, we can achieve our goal easier? For ex if cheese has 2 cats: Food and Diary, we can separate it and have 2 cheeses, one with cat food and one with cat diary. When we build up our output sets, we make sure that items with same names does not go inside single set. And, of course, we will be following blueprint for output. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <https://gist.github.com/a0341ed921167da438b3030468abaec3?email_source=notifications&email_token=AC5GJTJZVGGDNFKRLTL7273P4WMZRA5CNFSM4H3VRTZ2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAFUN26#gistcomment-2956207>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AC5GJTPXJKSM5ZVY5GVGDJDP4WMZRANCNFSM4H3VRTZQ> .

Here is the example showing why your solution isn't optimal.

https://awwapp.com/b/uuyfktgxv/

Here is a video going through the example:

https://drive.google.com/open?id=1MSMHb16K5D17ul1LBMCwlRkcC93uokQF

I have figured out a solution I am writing the code now will notify you when done.