̰

收集的C语言算法程序

贪心算法求解背包问题(C语言)2008年09月10日 星期三 09:20
/*
============================================================================
Name        : 贪心算法.c
Author      : dvdface
Version     :
Copyright   : Your copyright notice
Description : Hello World in C, Ansi-style 超无敌傻x贪心算法。贪心算法类似于启发算法。
============================================================================
*/

#include <stdio.h>
#include <stdlib.h>

//测试数据
int p[] ={25, 24, 15}; //货物的价值
int w[] ={18, 15, 10}; //货物的重量
const int N = 3; //货物种类的总数
const int M = 20; //背包的大小

//打印size大小的double数组
void print(double* array, int size) {
int i;
for(i=0; i<size; i++) {
   printf("%.2lf ", array[i]);
}
printf("\n");
}

//寻找数组中的最大值，并返回其下标
int findMax(double* array, int size) {
int i, pos;
double max = -1;
for(i=0; i<size; i++) {
   if(max < array[i]) {
    max = array[i];
    pos = i;
   }
}
return pos;
}

//贪心算法求解，返回double数组，每一个位对应着相应的货物要装入的比率
double* greedySolve(int* p, int* w, int n, int m) {
double* r = (double*)malloc(sizeof(double)*n);
double* s = (double*)malloc(sizeof(double)*n);
int i;
for(i=0; i<n; i++) {
   r[i] = p[i]/(w[i]*1.0);
}
print(r, n);
int remain;
int toFill;
for(i=0, remain=m; i<n && remain>0; i++) {
   toFill = findMax(r, n);
   r[toFill] = -1;
   if((remain - w[toFill]) >= 0) {
    s[toFill] = 1.0;
    remain = remain - w[toFill];
   } else {
    s[toFill] = (w[toFill] - remain)*1.0 / w[toFill];
    remain = 0;
   }
}
free(r);
return s;
}

int main(void) {
double* x = greedySolve(p, w, N, M);
print(x, N);
return EXIT_SUCCESS;
}