C++贪心算法实现部分背包问题

_(:з」∠)_

#include <cstdio>
#include <iostream>
#include <ctime>
#include <windows.h>
#include <algorithm>
#include <fstream>
using namespace std;
struct object
{
    int no;
    double weight;
    double value;
    double average;
};
bool cmp(const object &x, const object &y)
{
    return x.average > y.average;//从小到大排<,若要从大到小排则>
}
void greedySelector(int m,int W,int solution[],struct object object[]){
    int i = 0,V = 0,j = 0;
    while(object[i].weight < W)
    {
          solution[i] = 1;
          W = W - object[i].weight;
          V = V + object[i].value;
          i++;
    }
    V = V + (W/object[i].weight)*object[i].value;
    solution[i] = 1;
    cout << "The corresponding value of the optimal option is:" << V << endl;
    /*for( i = 0; i < m; i++)
    {
        if(solution[i] == 1)
        {
            cout << object[i].no << endl;
        }
    }*/
}
int main(void)
{
    LARGE_INTEGER nFreq;
    LARGE_INTEGER nBeginTime;
    LARGE_INTEGER nEndTime;
    ofstream fout1;
    ofstream fout2;
    srand((unsigned int)time(NULL));
    int m,i,j,t;
    double W;
    double cost;
    cout << "Please enter the number of times you want to run the program:";
    cin >> t;
    fout1.open("backpack-object.txt",ios::app);
    if(!fout1){
        cerr<<"Can not open file ‘backpack-object.txt‘ "<<endl;
        return -1;
    }
    fout1.setf(ios_base::fixed,ios_base::floatfield);       //防止输出的数字使用科学计数法
    fout2.open("backpack-weight.txt",ios::app);
    if(!fout2){
        cerr<<"Can not open file ‘backpack-weight.txt‘ "<<endl;
        return -1;
    }
    fout2.setf(ios_base::fixed,ios_base::floatfield);       //防止输出的数字使用科学计数法
    for (j = 0;j < t;j++)
    {
        cout << "——————————————————The "<< j + 1 << "th test —————————————————"<<endl;
        m = 1 + rand()%100000;      //物品个数
        W = 10 + rand()%100000;    //背包总重量
        fout1 << m << ",";
        fout2 << (int)W << ",";
        int solution[m];
        object object[m];
        for( i = 0;i < m;i++)
        {
            object[i].no = i + 1;
            object[i].value = 1 + rand()%10000;
            object[i].weight = 1 + rand()%10000;
            object[i].average = object[i].value/object[i].weight;
        }
        QueryPerformanceFrequency(&nFreq);
        QueryPerformanceCounter(&nBeginTime);
        sort(object,object + m,cmp);
        greedySelector(m,W,solution,object);
        QueryPerformanceCounter(&nEndTime);
        cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;
        fout1 << cost << endl;
        fout2 << cost << endl;
        cout << "The running time is:" << cost << " s" << endl;
    }
    fout1.close();
    fout2.close();
    cout << endl;
    cout << "Success!" << endl;
    return 0;
}

相关推荐