实现分数背包

Question

我试图通过首先根据对象的价值与对象的重量的比率对元素进行排序来实现分数式背包。我正在使用成对向量，其中成对的第一个元素是对象的值，成对的第二个元素是权重。 compbyrat 函数是通过值与权重的比来比较向量元素。我在 code.Can 以下出现运行次错误谁能帮我找出错误？

#include <iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
bool compbyrat(const pair<long long int,long long int> &a, const pair<long long int,long long int> &b)
{
    return ((double)a.first/(double)a.second)< ((double) b.first/(double) b.second) ;
}
int main() {
    long long int n, weight;
    vector<pair<long long int,long long int> > v;
    cin>>n>>weight;
    for(long long int i = 0; i < n; i++){
        cin>>v[i].first>>v[i].second;
    }

    sort(v.begin(), v.end(), compbyrat);
    long long int currentweight = 0, ans =0;
    for(long long int i =0; i < n && currentweight < weight; i++){
        if(currentweight + v[i].second <= weight){
            ans = ans + v[i].first;
        }
        else{
            ans = ans + (((double)v[i].first/(double)v[i].second) * (weight -currentweight));
        }
    }
    cout<<ans;
    return 0;
}

Answer 1

我可以通过一些修改来解决它。代码如下，

#include <iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<iomanip>
using namespace std;
bool compbyrat(const pair<long long int,long long int> &a, const pair<long long int,long long int> &b)
{
    return ((double)((double)a.first/(double)a.second)> (double)((double) b.first/(double) b.second)) ;
}
int main() {
    long long int n, weight;
    cin>>n>>weight;

    vector<pair<long long int,long long int> > v(n+2);
    for(long long int i = 0; i < n; i++){
        cin>>v[i].first>>v[i].second;
    }

    sort(v.begin(), v.end(), compbyrat);
    //cout<<v[0].first;
    long long int currentweight = 0;
    double ans = 0.0000;
    for(long long int i =0; i < n && currentweight < weight; i++){
        if(currentweight + v[i].second <= weight){
            ans = ans + v[i].first;
            currentweight = currentweight + v[i].second;
            //cout<<v[i].first<<" "<<v[i].second<<endl;
        }
        else{
            ans = ans + ((double)((double)v[i].first/(double)v[i].second) * (weight -currentweight));
            currentweight = currentweight + v[i].second;
        }


    }
    cout<<fixed << setprecision(4)<<ans;
    return 0;
}

实现分数背包

Implement Fractional knapsack

c++

algorithm

stl

knapsack-problem