Knapsack Greedy Algorithm- what am I doing wrong?

Question

What I have so far:

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <string>

using namespace std;

int main () {
    string line;
    int weightCapacity;
    int numItems;
    double weight, value;
    map<double,int> set;
    vector<int> w;
    vector<int> v;
    vector<int> knapsack;
    int bestValue = 0;
    int subsetValue = 0;
    int subsetWeight = 0;
    int i;
    vector<int> items;

    ifstream myFile ("knapsack.txt");

    // reading a text file
    if (myFile.is_open()) {
        cout << "Open" << endl;
    }

    else cout << "Unable to open file";

    myFile >> weightCapacity;
    myFile >> numItems;

    cout << weightCapacity << endl;
    cout << numItems << endl;

    for (i = 0; i < numItems; i++) {
        myFile >> weight;
        myFile >> value;
        set[value/weight] = i;
        w.push_back(weight);
        v.push_back(value);
        cout << weight << " " << value << endl;
    }


    int currentW = weightCapacity;
    int totalValue = 0;
    for (auto iter = set.rbegin(); iter != set.rend(); ++iter) {
        cout << iter->first << ": " << iter->second << endl;
        int W = w.at(iter->second);
        if (W <= currentW) {
            items.push_back(iter->second);
            totalValue += v.at(iter->second);
            currentW = currentW - W;
        }
    }
    cout << totalValue << endl;
    for(i=0; i < items.size(); i++) {
        cout << items.at(i) << ' ';
    }

Input file: https://d1b10bmlvqabco.cloudfront.net/paste/jky8a86gte072v/c4b0a8df58cfdc76a2e0a3881ec10a9a0b4096bc7107b740aaaea1ff745a2c81/Heur0.txt

My output:

2635

782 765 741 862 727 770 394 386 71 535 844 941 789 610 874 777 412 771 358 607 276 235 329 216 790 700 541 842 229 878 753 344 939 742 430 960 582 918 55

What it should be:

2851

72 217 224 230 236 277 320 330 359 387 392 395 413 536 542 586 608 611 619 629 632 701 728 742 748 766 771 772 778 783 790 791 843 845 863 875 879 942

Explanation of the algorithm:

Answer 1

I have couple of observations about your solution.

1. You used C++ map where "key" is the ratio of value per weight and the "value" is the item's id (the position of the item in the original order). So, what if two items have same value per weight? In that case, the map will only keep the one that comes later. This will potentially damage your solution.
2. The Algorithm 2 in your post suggest you need to sort (i) by decreasing order of item.value / item.weight and (ii) in case of ties, by decreasing order of item.value. You didn't consider (ii) in your solution.

I tried to fix the issues here:

#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

#define myFile myFile

bool comp(const pair<double, pair<int, int>> &i1, pair<double, pair<int, int>> &i2) {
    if(i1.first == i2.first) return (i1.second.second > i2.second.second);
    return (i1.first > i2.first);
}

int main () {
    string line;
    int weightCapacity;
    int numItems;
    // double weight, value;
    int weight, value;
    map<double,int> set;
    vector<int> w;
    vector<int> v;
    vector<int> knapsack;
    int bestValue = 0;
    int subsetValue = 0;
    int subsetWeight = 0;
    int i;
    vector<int> items;
    
    vector<pair<double, pair<int, int>>> wv_ratio;

    ifstream myFile ("Heur0.txt");

    // reading a text file
    if (myFile.is_open()) {
        cout << "Open" << endl;
    }

    else cout << "Unable to open file";

    myFile >> weightCapacity;
    myFile >> numItems;

    // cout << weightCapacity << endl;
    // cout << numItems << endl;

    for (i = 0; i < numItems; i++) {
        myFile >> weight;
        myFile >> value;
        //set[value/weight] = i;
        wv_ratio.push_back(make_pair((value/(double) weight), make_pair(i, value)));
        w.push_back(weight);
        v.push_back(value);
        //cout << weight << " " << value << endl;
    }

    sort(wv_ratio.begin(), wv_ratio.end(), comp);

    int currentW = weightCapacity;
    int totalValue = 0;
    //for (auto iter = set.rbegin(); iter != set.rend(); ++iter) {
    for (auto tmp = wv_ratio.begin(); tmp != wv_ratio.end(); ++tmp) {
        pair<double, pair<int, int>> iter = (pair<double, pair<int, int>>) *(tmp);
        //cout << iter->first << ": " << iter->second << endl;
        cout << iter.second.first << ": " << iter.first << " " << iter.second.second << endl;
        int W = w.at(iter.second.first);
        if (W <= currentW) {
            items.push_back(iter.second.first);
            totalValue += v.at(iter.second.first);
            currentW = currentW - W;
        }
    }
    cout << totalValue << endl;
    for(i=0; i < items.size(); i++) {
        cout << items.at(i) << ' ';
    }
    
    return 0;
}

And it produce the output like this:

2889

782 585 765 741 628 862 618 727 770 394 386 71 535 844 941 789 610 874 777 412 771 319 358 391 607 276 235 223 329 216 790 747 631 700 541 842 229 878 344       

Clearly it does not match with your expected one. But, I am pretty sure the code that I am sharing here works according to the Algorithm 2 of your post. I would like to suggest you to debug with smaller sized input, if you think your expected output is absolutely correct and can be achieved by following the Algorithm 2.