算法提高 求最大值

问题描述

　　给n个有序整数对ai bi，你需要选择一些整数对 使得所有你选定的数的ai+bi的和最大。

    并且要求你选定的数对的ai之和非负，bi之和非负。

输入格式

　　输入的第一行为n，数对的个数

　　以下n行每行两个整数 ai bi

输出格式

　　输出你选定的数对的ai+bi之和

样例输入

5

-403 -625

-847 901

-624 -708

-293 413

886 709

样例输出

1715

数据规模和约定

　　1<=n<=100

　　-1000<=ai,bi<=1000

 

01背包变种，复制一下别人的思路：

不直接计算选定的数的ai+bi的和，而是转化为计算在ai的和一定的情况下尽量使选定的bi的和最大。于是变成为一个和01背包差不多的问题。首先过滤掉所有ai和bi均小于0的数对，令dp[i][j]表示前i个数对，选定的ai的和为j的情况下bi的和的最大值，将dp[i][j]初始化为-INF，再将所有已知合法情况初始化：dp[i][a[i]] = b[i]，之后dp[i][j] = max(dp[i - 1][j], dp[i][j])，若j - a[i]存在，dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + b[i])。为避免负数作为数组下标，要加一个偏移量。

来源： http://www.cnblogs.com/wangyiming/p/6476019.html

 

 

#include<stdio.h>

#define Max(a,b)  ((a>b)?(a):(b))
#define N  100000

void input( int [] , int [] , int );
int maxNum( int [] , int [] , int );

int main(void)
{
    int n ;
    scanf("%d" , &n );
    
    int Na[n] , Nb[n] ;
    input( Na , Nb , n );
    
    int ans = maxNum( Na , Nb , n );
    printf("%d\n", ans >= 0 ? ans : 0 ); 
    return 0;    
}

void input( int Na[] , int Nb[] , int n ){
    while( n -- ){
        scanf("%d%d", Na ++ , Nb ++ );
    }
}

int maxNum( int Na[] , int Nb[] , int n ){
    static int dp[100][N*2+1] = {0} ;
    int res = -N ;
    int i , j ;
    for( i = 0 ; i < n ; i ++ ){
        for( j = -N ; j <= N ; j ++ ){
            dp[i][j + N] = -N ;
        }
    }
    
    for( i = 0 ; i < n ; i ++ ){
        dp[i][N + Na[i]] = Nb[i] ; 
    }
    
    for( i = 1 ; i < n ; i ++ ){
        for( j = -N ; j <= N ; j ++ ){
            dp[i][j + N] = Max(dp[i][j + N] , dp[i-1][j + N]);
            
            if( j + N - Na[i] >= 0 && j + N - Na[i] < N*2 ){
                dp[i][j + N] = Max( dp[i][j + N] , dp[i-1][j + N - Na[i]] + Nb[i] );
            }
        }
    }
    
    for( j = 0 ; j <= N ; j ++ ){
        if( dp[n-1][j + N] >= 0 ){
            res = Max( res , j + dp[n-1][j + N] );
        }
    }
    
    return res;
}