最优装载问题--贪心算法

#include<iostream>#include<string>#include<memory.h>#include<cstdio>#include<string>#include <algorithm>#define NUM 1001using namespace std;int charaNum[NUM] ;//存放输入数据的数组int tempArr[NUM];struct load{    int weight;    int index;}arr[NUM];int x[NUM];bool cmp(const load & a, const load & b){    return a.weight<b.weight? true: false;}int greedySelect(load * A ,int num,int c){    int sum = 0;    int cleft = c;    int i = 0;    while(i<num && cleft>=A[i].weight)    {        cleft-=A[i].weight;        sum++;        x[A[i].index] = 1;        i++;    }    return sum;}int main(){    freopen("in.txt","r",stdin);    int weight ;    int num;    while(cin>>weight>>num)    {        memset(x,0 ,sizeof(x));        for(int i= 0;i<num;i++)        {            cin>>arr[i].weight;            arr[i].index=i;        }        stable_sort(arr,arr+num,cmp);        int sum = greedySelect(arr,num,weight);        if(sum == 0)        {            cout<<"No answer!"<<endl;        }        else        {            cout<<sum<<endl;        }        for(int i = 0;i<num;i++)        {            if(x[i] == 1)            {                cout<<i+1<<" ";            }        }        cout<<endl;    }}

输入：

50 340 10 4037 510 30 24 35 4025 330 40 50

输出：

2
1 2
2
1 3
No answer!