prob 1018 DP(动态规划)

每一个状态b，表示最后的产品的B值就是b，所以，只要考虑把满足状态b的所有选择中的p值最小的部件
选出来就可以了。那么总的P值也一定是最小的，最后的B/P值一定是最大的。

算法实现：
for(i=0;i<总共的状态数;i++)
{	for (j=0;j<总的部件数;j++)
	{	for(k=0;k<总的选择;k++)
			求出满足状态i的，p值最小的部件;
           total+=求出来的p；
     }
     比较求出最大的B[i]/ total 的值；
}

效率分析：
总状态数*部件数*每个部件的选择数

        
解题总结：
        动态规划要灵活运用
	
	在有两个属性值的情况下，必须要固定一个求另一个，同时规划两个值的最优是不可行的。

	找清状态，通常可能做状态的是：属性值，或者属性值的差，和，积（如jury）

	状态转换不一定非要用二维数组自底向上去推

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

#define MAX 100
struct bp_node{
        int b;
        int p;
}bp[MAX][MAX];

int m;
int num[MAX];
int b[MAX*MAX];
int cb;

static int compare(const void *x, const void *y);
static void input_init(void);
static void work(void);
int main(int argc, char **argv)
{
        int tests;

        scanf("%d ", &tests);
        while(tests--){
                input_init();
                work();
        }
        exit(0);
}


static int compare(const void *x, const void *y)
{
        return (*((int *)x) - *((int *)y));
}

static void input_init(void)
{
        int i, j;

        scanf("%d", &m);
        getchar();
        for(i = 0; i < m; i++){
                scanf("%d ", &num[i]);
                for(j = 0; j < num[i]; j++){
                        scanf("%d %d", &bp[i][j].b, &bp[i][j].p);
                        b[cb++] = bp[i][j].b;
                }
                getchar();
        }
        qsort(b, cb, sizeof(b[0]), compare);
}

static void work(void)
{
        int i, j, k, s, total;
        float max = 0.0;

        for(i = 0; i < cb; i++){
                if(b[i] == b[i+1]){
                        continue;
                }
                total = 0;
                for(j = 0; j < m; j++){
                        s = 32767;
                        for(k = 0; k < num[j]; k++){
                                if((bp[j][k].b >= b[i]) && (bp[j][k].p <= s)){
                                        s = bp[j][k].p;
                                }
                        }
                        total += s;
                }
                if(max < (float)b[i]/total){
                        max = (float)b[i]/total;
                }
        }
        printf("%.3f\n", max);
}