HDOJ1009

   要尽情的享受学习的过程！

         昨天在听报告的时候学习了贪心算法，今天终于写了一到关于贪心算法的题目，虽然是最简单的。题目是典型的部分背包问题。用了一下快速排序。从中学到了如何对结构体进行排序，还有双精度的排序。因为cmp函数的返回值只能是int型的，所以不能只有一个return a-b ; ，是要返回一个整数的。所以就要判断一下就可以了，可以用一个开关语句就可以了。

#include <stdio.h>
#include <stdlib.h>
#define N 1010

typedef struct link{
    int j ;
    int f ;
    double price ;
}Food ;

int cmp( const void *a, const void *b )
{
    return (*(link *)a).price < (*(link *)b).price ? 1 : -1 ;
}

int main( void )
{
    int i, m, n ;
    double max ;
    Food food[N] ;
    
    while( scanf("%d%d", &m, &n) && !(m==-1&&n==-1 )){      
        for( i=0; i<n; ++i ){
            scanf("%d%d", &food[i].j, &food[i].f ) ;
            food[i].price = (double)food[i].j / (double)food[i].f ;
        }
        qsort( food, n, sizeof(food[0]), cmp );
        max = 0.0 ;
        for( i=0; m>0&&i<n; ++i ){ 
            if( m >= food[i].f )
            max += (double)food[i].j ; 
            else
            max += (double)m*food[i].price ;  
            m -= food[i].f ;
        }
        printf("%.3lf\n", max );
    }        
        
    system("pause") ;
    return 0 ;
}

HDOJ1009,布布扣,bubuko.com

HDOJ1009

原文：http://www.cnblogs.com/ct0421/p/3608866.html