贪心算法部分背包问题

Question

洛谷原题：https://www.luogu.com.cn/problem/P2240
贪心算法，先读入并计算性价比，根据性价比排序后从头开始装包，能过样例但是测试数据WA

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int N,T;
int m[102],v[102];
double e[102];
double M=0;

double tanxin(int N,int T){
    for(int i=1;i<N;i++)for(int j=N;j>1;j--)if(e[j]>e[j-1]){
        swap(e[j],e[j-1]);
        swap(m[j],m[j-1]);
        swap(v[j],v[j-1]);
    }
    for(int i=1;i<=N;i++){
        if(m[i]<=T){
            M+=v[i];
            T-=m[i];
        }else{
            M+=e[i]*T;
            break;
        }
    }
    return M;
}

int main(){
    cin>>N>>T;
    for(int i=1;i<=N;i++){
    cin>>m[i]>>v[i];
    e[i]=v[i]/m[i];
    }    
    printf("%.2lf",tanxin(N,T)); 
    return 0;
} 

Answer 1

“Devil组”引证GPT后的撰写：
存在以下问题：

• 内部排序时，数组下标从1开始，导致排序时下标越界；

• 排序循环范围应该是从1到N，而不是从1到N-1，否则最后一个元素没有排序；

• 背包装满后，应该立即结束，不应该继续放物品

修改如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n, T;
int m[N], v[N];
double e[N];

bool cmp(int a, int b) {
    return e[a] > e[b];
}

int main() {
    cin >> n >> T;
    for (int i = 1; i <= n; i++) {
        cin >> m[i] >> v[i];
        e[i] = 1.0 * v[i] / m[i];
    }
    int id[N];
    for (int i = 1; i <= n; i++) id[i] = i;
    sort(id + 1, id + n + 1, cmp);
    double ans = 0;
    for (int i = 1; i <= n && T; i++) {
        int j = id[i];
        int t = min(T, m[j]);
        ans += t * e[j];
        T -= t;
    }
    printf("%.2lf", ans);
    return 0;
}