algorithm - 获取 k 个整数，使得列表之和的比率最大

Question

给定 2 个长度为 N 的整数数组 a 和 b，其中 a[i] 表示第 i 个建筑物的面积，b[i] 表示第 i 个建筑物的价格，选择 k 个建筑物，使得这些建筑物的价格/这些建筑物的面积总和（总价格与总面积的比率）是最大值。

有人可以提出解决这个问题的方法吗？我在测试中得到了这个并且无法解决它。

标签： algorithmrecursiondynamic-programming

Answer 1

为了解决这个问题递归，当您位于数组的第 i 个索引处时，您可以选择该建筑物并考虑其价格和面积以获得最终答案，或者您可以忽略该建筑物并移至下一个索引。

因此，每当我们选择任何建筑物时，都会增加area_till_now当前建筑物的面积并增加当前建筑物price_till_now的价格并减少remaining_k1。

(0-based indexing)
double ans=0;
        
void recur(int current_index,double price_till_now,double area_till_now,int remaining_k){
     
    // we have selected k buildings.
    // so simply find the ratio and update maximum answer possible          
    if(remaining_k==0){
        double ratio=price_till_now/area_till_now;
        ans=max(ans,ratio);
        return;
    }
    // if we reach end of our array,
    // return as we cant select any more building
    if(current_index==n)return;

    // recur without selecting this building
    recur(current_index+1,price_till_now,area_till_now,left);

    // recur after selecting this building
    recur(current_index+1,price_till_now+price[current_index],area_till_now+area[current_index],left-1));
}

由于每座建筑物都有两种选择，因此它将具有 O(2^n) 时间复杂度。

更新： - 我早期的 dp 解决方案有错误的计算。很快我将更新优化和正确的 dp 解决方案。