贪心算法求解背包问题_衡的博客_贪心算法解决背包问题

#include<iostream>
using namespace std;
typedef struct {
    float p;		// 物体的价值
    float w;		// 物体的重量 
    float v;		// 物体的价值重量比 
} OBJECT;
void bubble_sort(OBJECT A[], int n) {
    OBJECT t;
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (A[j].v < A[j + 1].v) {
                t = A[j];
                A[j] = A[j + 1];
                A[j + 1] = t;
            }
        }
    }
}
float knapsack_greedy(float M, OBJECT instance[],
    float x[], int n)
{
    int i;
    float m, p = 0;
    for (i = 0; i < n; i++)//计算物体的价值重量比
    {
        instance[i].v = instance[i].p / instance[i].w;
        x[i] = 0;  //解向量赋初值  
    }
   bubble_sort(instance, n); /*按关键值v的递减顺序排序物体*/
    m = M;   //背包的剩余载重量 
    for (i = 0; i < n; i++)
    {
        if (instance[i].w <= m) //优先装入价值重量比大的物体 
        {
            x[i] = 1;
            m -= instance[i].w;
            p += instance[i].p;
        }
        else
        {    //最后一个物体的装入分量 
            x[i] = m / instance[i].w;
            p += x[i] * instance[i].p;
            break;
        }
    }
    return p;
}
int main()
{
    int  N;
    cout << "共有N个物体：";
    cin >> N;
    OBJECT* instance = new OBJECT[N];    // 存放n个物体
    float* x = new float[N];			  // n个物体装入背包的份量 
    float M = 100;                         //背包的载重量
    cout << "输入N个物体的价值：";
    for (int i = 0; i < N; i++)
        cin >> instance[i].p;
    cout << "输入N个物体的重量：";
    for (int j = 0; j < N; j++)
        cin >> instance[j].w;
    cout << endl << "输出N个物体的价值重量比：";
    for (int i = 0; i < N; i++)
        instance[i].v = instance[i].p / instance[i].w;    /*计算物体的价值重量比*/
    for (int i = 0; i < N; i++)
        cout << instance[i].v << " ";
    cout << endl << "背包问题的最优解为：" << knapsack_greedy(M, instance, x, N);
    cout << endl << "N个物体被装入背包的分量为：";
    for (int i = 0; i < N; i++)
        cout << x[i] << " ";
    cout << endl << endl;
    return 0;
}#include<iostream>
using namespace std;
typedef