c++ - 背包贪婪算法-我做错了什么？

Question

到目前为止我所拥有的:

#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) << ' ';
    }

输入文件:
https://d1b10bmlvqabco.cloudfront.net/paste/jky8a86gte072v/c4b0a8df58cfdc76a2e0a3881ec10a9a0b4096bc7107b740aaaea1ff745a2c81/Heur0.txt
我的输出:
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
它应该是什么:
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
算法说明:

Answer 1

我对您的解决方案有几点看法。

你用过 C++ map其中“key”是value per weight的比率而“值”是 item's id (项目在原始订单中的位置)。那么，如果两个项目具有相同的 value per weight 呢？ ?在这种情况下， map 将只保留稍后出现的 map 。这可能会损坏您的解决方案。

Algorithm 2在您的帖子中建议您需要按 item.value / item.weight 的降序对 (i) 进行排序(ii) 在平局的情况下，按 item.value 的降序排列.您在解决方案中没有考虑 (ii)。

我试图在这里解决问题:

#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;
}

它产生这样的输出:

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       

显然它与您的预期不匹配。但是，我很确定我在这里分享的代码是根据 Algorithm 2 工作的。你的帖子。如果您认为您的预期输出绝对正确并且可以通过遵循 Algorithm 2 来实现，我建议您使用较小尺寸的输入进行调试。 .