1

So I am trying to solve a 0-1 KnapSack problem. I would like to have an empty vector or array that gets filled after the user gets prompted to select items. While I can get it running with set values I'm having trouble actually pushing the users input into the vector and then passing it into my KnapSack function.

#include <vector>
#include <bits/stdc++.h>
#include <queue>

using namespace std;

// Structure for an item which stores weight and corresponding
// value of Item

struct TarkovItems {

    int value, size;

    // Constructor

    TarkovItems(int value, int size) : value(value), size(size) {}

};

// Comparison function to sort Item according to val/weight ratio

bool cmp(struct TarkovItems a, TarkovItems b) {

    int r1 = (int) a.value / a.size;

    int r2 = (int) b.value / b.size;

    return r1 > r2;

}

// Main function to solve problem

int TarkovAlgorithm(int W, TarkovItems ItemArray[], int n) {

    //    sorting Item on basis of ratio

    sort(ItemArray, ItemArray + n, cmp);

    int curWeight = 0; // Current weight in knapsack

    int finalvalue = 0; // Result (value in Knapsack)


    // Looping through all Items

    for (int i = 0; i < n; i++) {

        // If adding Item won't overflow, add it completely

        if (curWeight + ItemArray[i].size <= W) {

            curWeight += ItemArray[i].size;

            finalvalue += ItemArray[i].value;

        }


    }

    // Returning final value

    return finalvalue;

}

// driver program to test above function

int main() {

    int userInputForBackpack;
    int userInputForItems;

    TarkovItems ItemArray[] = {{10, 20},{5,  30}};  //I would like to not hard code these values


    cout << "Are you using 1. A Raid Backpack, 2. A Berkut Backpack or 3. A Tactical Sling? "
         << "Please enter 1, 2, or 3." << endl;
    cin >> userInputForBackpack;
    switch (userInputForBackpack) {

        case 1:

            userInputForBackpack = 48;
            cout << "You selected Raid Backpack of size 48" << endl;
            break;

        case 2:

            userInputForBackpack = 20;
            cout << "You selected Berkut Backpack of size 20" << endl;
            break;


        case 3:

            userInputForBackpack = 6;
            cout << "You have selected a Tactical Sling of size 6" << endl;
            break;

    }

    cout << "Enter the number for each item you found. Type 0 to quit adding items." << endl;
    cout << "1. Mdr Assault rifle, 2. AS VAL. 3. VSS Vintorez " << endl;

    cin >> userInputForItems;

    //This is where I am having trouble allowing the user to select items and then
    //pushing them into the array.

    int n = sizeof(ItemArray) / sizeof(ItemArray[0]);

    cout << "Maximum value we can obtain = "

         << TarkovAlgorithm(userInputForBackpack, ItemArray, n);

    return 0;

0 Answers0