【動态規劃】——POJ 1018 Communication System

轉載請注明出處：http://blog.csdn.net/a1dark

分析：這題其實可以用搜尋寫、以前用搜尋做過這道題、不過既然是練DP、那便DP吧、

//dp[i][j]表示選了前i件商品，最小帶寬為j時的價值總和
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=105;
const int maxm=10005;
int b[maxn];
int p[maxn];
int dp[maxn][maxm];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        memset(dp,-1,sizeof(dp));
        scanf("%d",&n);
        int maxb=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&m);
            for(int j=1;j<=m;j++){
                scanf("%d%d",&b[j],&p[j]);
                maxb=max(maxb,b[j]);
            }
            if(i==1){//第一層直接初始化
                for(int j=1;j<=m;j++)
                    dp[i][b[j]]=p[j];
                continue;
            }
            for(int k=0;k<=maxb;k++){
                if(dp[i-1][k]==-1)continue;
                for(int j=1;j<=m;j++){
                    int mb=min(k,b[j]);//當選擇第J個廠商時、取目前最小的帶寬
                    if(dp[i][mb]==-1)//如果這種帶寬沒有别的組合達到、則直接由上一層加
                        dp[i][mb]=dp[i-1][k]+p[j];
                    else//如果這種組合已經有值了、則選擇小的
                        dp[i][mb]=min(dp[i][mb],dp[i-1][k]+p[j]);
                }
            }
        }
        double ans=0;
        for(int i=0;i<=maxb;i++)//周遊每一種帶寬的對應的最小總價格
            ans=max(ans,(1.0*i)/(double)dp[n][i]);
        printf("%.3f\n",ans);
    }
    return 0;
}