Solution for promotion for EPOS C++

promotion_solution_knapsack_01.cpp

#include <bits/stdc++.h>
using namespace std;

//Idea:
//1. Sort the list by input descending 
//2. Get all inputs of the list item after sorted
//3. Get indexes list of item want to pick
//4. For each index in the list, get item at that index

//Time complexcity Worst case: O(N * Sum). N is the length of the array. Sum is the total value of the array
//Space Complexity: O[N][Sum]

struct Item {
  char name;
  int input;
};

int max(int a, int b) { return (a > b) ? a : b; }
 
vector<int>  findAllItemIndexInKnapSack(int W, vector<int> val, int n)
{
    int i, w;
    int sum = 0;
    for(int i =0; i < n ;i++) {
        sum += val[i];
    }
    
    if (sum < W) return  {};
    
    int K[n + 1][sum + 1];
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= sum; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (val[i - 1] <= w)
                K[i][w] = max(val[i - 1] +
                    K[i - 1][w - val[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
    
    int res;
    bool haveRes = false;
    for(int i = sum; i >0; i--) {

        if (K[n][i] > W) 
        {
            if (K[n][i] % W ==0) 
            {
                res = K[n][i];
                haveRes = true;
            }
            if (haveRes == false) {
                res = K[n][i];
            }
        }
        else if (K[n][i] == W ) {
            res = K[n][i];
        }
       
    }
    vector<int> item_indexes;
    for (i = n; i > 0 && res > 0; i--) {
        if (res == K[i - 1][res])
            continue;       
        else {
            printf("%d", val[i - 1]);
            printf("(%d)    ", i-1);
            item_indexes.push_back(i-1);
            res = res - val[i - 1];
        }
    }
    return item_indexes;
}
 
void printArray(vector<int> arr) {
    for(auto itr : arr)
    cout << itr << " ";
}

void printListItem(vector<Item> item_list) {
    for(auto ite : item_list) {
        cout << ite.name << ": " << ite.input << endl;
    }
}

bool compareByInput(const Item &a, const Item &b)
{
    return a.input > b.input;
}

vector<Item> createListItem(vector<char> item_name, vector<int> input)
{
    vector<Item> list_item;
    for(int i =0; i < input.size(); i++) {
           list_item.push_back({item_name[i], input[i]});
    }
    return list_item;
}

vector<int> getListItemInputAfterSort(vector<Item> item_list)
{
    vector<int> inputs;
    for(auto ite : item_list) {
        inputs.push_back(ite.input);
    }
    return inputs;
}

int main()
{
    vector<char> item_name = {'A','B','C','D','E'};
    vector<int> input1 = {3,5,1,6,2};
    vector<int> input2 = {3,5,7,6,6};
    vector<int> input3 = {6,6,7,4,5};
    vector<int> input4 = {11,4,4,5,6};
    vector<int> input5 = {6,7,8,1,1};
    vector<int> input6 = {6,6,6,6,6};
    int W = 12;
    
    //Create list item from name and input
    vector<Item> list_item1 = createListItem(item_name, input1);
    vector<Item> list_item2 = createListItem(item_name, input2);
    vector<Item> list_item3 = createListItem(item_name, input3);
    vector<Item> list_item4 = createListItem(item_name, input4);
    vector<Item> list_item5 = createListItem(item_name, input5);
    vector<Item> list_item6 = createListItem(item_name, input6);

    cout << "Input 1: " <<endl;
    printArray(input1);
    cout<<endl;
    sort(list_item1.begin(), list_item1.end(), compareByInput);
    vector<int> inputAfterSort = getListItemInputAfterSort(list_item1);
    vector<int> item_indexes = findAllItemIndexInKnapSack(W,  inputAfterSort, inputAfterSort.size());
    cout <<endl<< "List item: " << endl;
    for(auto i: item_indexes) {
        cout << list_item1[i].name << "  " << list_item1[i].input << endl;
    }
    
    cout <<endl << endl;
    cout << "Input 2: " <<endl;
    printArray(input2);
    cout<<endl;
    sort(list_item2.begin(), list_item2.end(), compareByInput);
    vector<int> inputAfterSort2 = getListItemInputAfterSort(list_item2);
    vector<int> item_indexes2 = findAllItemIndexInKnapSack(W,  inputAfterSort2, inputAfterSort2.size());
    cout <<endl<< "List item: " << endl;
    for(auto i: item_indexes2) {
        cout << list_item2[i].name << "  " << list_item2[i].input << endl;
    }

    cout <<endl << endl;
    cout << "Input 3: " <<endl;
    printArray(input3);
    cout<<endl;
    sort(list_item3.begin(), list_item3.end(), compareByInput);
    vector<int> inputAfterSort3 = getListItemInputAfterSort(list_item3);
    vector<int> item_indexes3 = findAllItemIndexInKnapSack(W,  inputAfterSort3, inputAfterSort3.size());
    cout <<endl<< "List item: " << endl;
    for(auto i: item_indexes3) {
        cout << list_item3[i].name << "  " << list_item3[i].input << endl;
    }
    
    cout <<endl << endl;
    cout << "Input 4: " <<endl;
    printArray(input5);
    cout<<endl;
    sort(list_item4.begin(), list_item4.end(), compareByInput);
    vector<int> inputAfterSort4 = getListItemInputAfterSort(list_item4);
    vector<int> item_indexes4 = findAllItemIndexInKnapSack(W,  inputAfterSort4, inputAfterSort4.size());
    cout <<endl<< "List item: " << endl;
    for(auto i: item_indexes4) {
        cout << list_item4[i].name << "  " << list_item4[i].input << endl;
    }


    cout <<endl << endl;
    cout << "Input 5: " <<endl;
    printArray(input5);
    cout<<endl;
    sort(list_item5.begin(), list_item5.end(), compareByInput);
    vector<int> inputAfterSort5 = getListItemInputAfterSort(list_item5);
    vector<int> item_indexes5 = findAllItemIndexInKnapSack(W,  inputAfterSort5, inputAfterSort5.size());
    cout <<endl<< "List item: " << endl;
    for(auto i: item_indexes5) {
        cout << list_item5[i].name << "  " << list_item5[i].input << endl;
    }
    
    cout <<endl << endl;
    cout << "Input 6: " <<endl;
    printArray(input6);
    cout<<endl;
    sort(list_item6.begin(), list_item6.end(), compareByInput);
    vector<int> inputAfterSort6 = getListItemInputAfterSort(list_item6);
    vector<int> item_indexes6 = findAllItemIndexInKnapSack(W,  inputAfterSort6, inputAfterSort6.size());
    cout <<endl<< "List item: " << endl;
    for(auto i: item_indexes6) {
        cout << list_item6[i].name << "  " << list_item6[i].input << endl;
    }

    return 0;
}