本文主要是介绍【POJ】2976 Dropping tests 01分数规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【POJ】2976 Dropping tests
题目大意：给你长度为n的一对整数a[],b[]（注意是一对的），根据式子可以得到：∑a[ i ] / ∑b[ i ]，现在给你整数k，你可以从n个中剔除k对，问剩下的根据式子能得到的最大值是多少，答案*100并且四舍五入精确到个位。
题目分析：
很清晰的01分数规划，设Q(L) = ∑a[ i ] - L * ∑b[ i ]。则Q(L) < 0时能得到更优解，Q(L) > 0时不能得到最优解，Q(L) = 0时是解。
用二分就Q(L) < 0的时候修改下界，Q(L) > 0的时候修改上界。注意精度问题即可。
二分代码如下：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )const int MAXN = 1005 ;
const double INF = 1e18 ;
const double eps = 1e-6 ;int a[MAXN] , b[MAXN] ;
double c[MAXN] ;
int n , k ;double solve ( double r ) {REP ( i , n )c[i] = a[i] - r * b[i] ;sort ( c , c + n ) ;double ans = 0 ;REPF ( i , k , n - 1 )ans += c[i] ;return ans ;
}void work () {while ( ~scanf ( "%d%d" , &n , &k ) && ( n || k ) ) {REP ( i , n )scanf ( "%d" , &a[i] ) ;REP ( i , n )scanf ( "%d" , &b[i] ) ;double l = 0 , r = INF , m ;while ( fabs ( r - l ) > eps ) {double m = ( l + r ) / 2 ;if ( solve ( m ) >= eps )l = m ;elser = m ;}printf ( "%d\n" , ( int ) ( 100 * l + 0.5 ) ) ;}
}int main () {work () ;return 0 ;
}然后是迭代的代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )const int MAXN = 1005 ;
const double INF = 1e18 ;
const double eps = 1e-5 ;struct Node {int a , b ;double c ;bool operator < ( const Node &t ) const {return c > t.c ;}
} ;Node node[MAXN] ;
int n , k ;double solve ( double r ) {REP ( i , n )node[i].c = node[i].a - r * node[i].b ;sort ( node , node + n ) ;double A = 0 , B = 0 ;REP ( i , n - k )A += node[i].a , B += node[i].b ;return A / B ;
}void work () {while ( ~scanf ( "%d%d" , &n , &k ) && ( n || k ) ) {REP ( i , n )scanf ( "%d" , &node[i].a ) ;REP ( i , n )scanf ( "%d" , &node[i].b ) ;double res = 0 , tmp ;while ( 1 ) {tmp = solve ( res ) ;if ( fabs ( res - tmp ) <= eps )break ;res = tmp ;}printf ( "%.0f\n" , 100 * res ) ;}
}int main () {work () ;return 0 ;
}这篇关于【POJ】2976 Dropping tests 01分数规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
