Why can't I solve 0-1 Knapsack with greedy approach?

Viewed 39

It says everywhere the greedy method is not optimal for 0-1 Knapsack problem. I wrote the following code, please explain why it is not good.

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> a1, pair<int,int> a2){
    return (a1.first)/(a1.second)>(a2.first)/(a2.second);
}

int main() {
    int n, W;
    cout<<"Enter length:";
    cin>>n;
    cout<<"Enter capacity:";
    cin>>W;
    vector<pair<int,int>> act;
    cout<<"Enter weight, value";
    for(int i=0; i<n; i++){
        int s,e;
        cin>>s>>e;
        act.push_back({s,e});
    }
    sort(act.begin(), act.end(),cmp);
    int val=0;
    int sum=0;
    for(int i=0; i<n; i++){
        if(sum+(act[i].second)<=W){
            sum+=act[i].second;
            val+=act[i].first;
        }
        if(sum==W)
            break;
    }
    cout<<val;
    return 0;

}
0 Answers
Related