ナップザックアルゴリズムでベクトルを使用しているときに不正なallocがスローされました

Question

現在、オンラインリソースの組み合わせによってデータ構造とアルゴリズムを試しています。その一つとして、有名なナップザック問題を貪欲なアルゴリズムで解決しようと試みました。
パフォーマンスを向上させるために、ループの前に問題の重みと値を降順でソートしています。
私はコードを実行すると、私はbad_allocを取得します。これは私が必要とするメモリを割り当てていないということですか？私は解決策を探していましたが、 "新しい"識別子でメモリに明示的にアクセスしているわけではないので、これまでのところ本当に役に立ちませんでした。ここで

はコードです：事前に

#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std; 

bool decreaseSort(int a, int b) 
{ 
    return a > b; //sort by decreasing value for better performance 
} 

double get_optimal_value(int capacity, vector<int> weights, vector<int> values) { 

sort(weights.begin(),weights.end(), decreaseSort); //sort weights 
sort(values.begin(),weights.end(), decreaseSort); //sort values 

vector<int> ourKnapsack(values.size()); //set Knapsack to n elements 

for (size_t i = 0; i < ourKnapsack.size(); i++) 
    ourKnapsack.push_back(0); //fill with zeroes 


double totalValue = 0.0; //total worth 
int ourInput = 0; //what we are putting in 

for (size_t j = 0; j < ourKnapsack.size(); j++){ 
    double unitValue = values.at(j)/weights.at(j); //ratio of value to weight for specific item 

    if (capacity == 0) 
     return totalValue; //end program, return value 


    if (weights.at(j) < capacity){ 
     ourInput = weights.at(j); //if we have room, fill with the weight 
    } 
    else { 
     ourInput = capacity; //fill the rest of the pack 
    } 


    totalValue = totalValue * (ourInput * unitValue); //update totalValue 
    weights.at(j)-=ourInput; //subtract weight by what we put in 
    ourKnapsack.at(j)+=ourInput; //update knapsack element 
    capacity-=ourInput; //shrink capacity 

} 
return totalValue; 
} 

int main() { 
int n = 3; //test case, 3 items, capacity of 50 
int capacity = 50; 

vector<int> values(n); 
values = {60,100,120}; 
vector<int> weights(n); 
weights = {20,50,30}; 

double optimal_value = get_optimal_value(capacity, weights, values); 

std::cout.precision(10); 
std::cout << optimal_value << std::endl; //should return optimal value 
return 0; 
} 

おかげ

Answer 1

for (size_t i = 0; i < ourKnapsack.size(); i++) 
    ourKnapsack.push_back(0); //fill with zeroes 

は、これは無限ループに入ります。