背包问题——贪心算法

// 分别以不同起点开始进行以当前最优的策略选择，直到依次遍历所有的开始点 // An highlighted block #include<stdio.h> #include<stdlib.h> #define MAXSIZE 60 bool HasExist(int Exist[],int len,int flag){ for (int i = 0; i < len; i++) { if(Exist[i]==flag) return true; /* code */ } return false; } ///贪心算法——背包问题 void GreedyAL(int weight[],int Value[],int len,int MaxWeigh){ int RValue[MAXSIZE]; //存放最优值 int RWeight[MAXSIZE]; //存放最大重量 int Exist[MAXSIZE][MAXSIZE]; //存放对应的下标 int flag = 0; for (int k = 0; k < len; k++) //进行len循环，从不同的价值点出发求解问题 { flag = 0; RValue[k] = Value[k]; RWeight[k] = weight[k]; Exist[k][flag++] = k; for(int i = 0;i<len;i++){ int max = -1; int fl = -1; for (int j = 0; j < len; j++) { if(weight[j]+RWeight[k]<=MaxWeigh&&k!=j){ //不超过最大值以及不等于本身时加入， if(HasExist(Exist[k],flag,j)){ //当前的节点是否已经添加到 continue; }else{ if(Value[j]>max) //获得最大的Value { max = Value[j]; //获取最大值 fl = j; //获取最大值下标 } } } } if(RWeight[k]>=MaxWeigh||fl==-1) //当质量超重时结束，或者背包未满但是没有合适的物品装入时也为结束 { Exist[k][flag] = -1; //作为结束符 break; } RWeight[k]+=weight[fl]; //加上当前的最大值Weight RValue[k] += max; //加上Value Exist[k][flag++] = fl; //加入当前的最优值下标 } } int max = 0; for (int i = 1; i < len; i++) { if(RValue[max]<RValue[i]){ //找到最大的那一个出发点所得到的序列 max = i; } } for(int i = 0 ;i < len ;i++){ printf("Start in %d-th Goods: ",(i+1)); for (int j = 0;Exist[i][j] != -1; j++) { printf("%d ",Exist[i][j]); /* code */ } printf("\nMaxValue : %d MaxWeigh : %d\n\n",RValue[i],RWeight[i]); } printf("MaxValue : %d MaxWeigh : %d\nBEST SUCCESSION : ",RValue[max],RWeight[max]); for (int i = 0; Exist[max][i]!=-1; i++) { printf("%d ",Exist[max][i]); } printf("\n"); } int main(){ int Weigh[]={35,30,60,50,40,10,25}; //质量集合 int Value[]={10,40,30,50,35,40,30}; //价值集合 int len = sizeof(Value)/sizeof(int); GreedyAL(Weigh,Value,len,155); //求解在最大质量150的情况下的最优序列 system("pause"); return 0; }