资源分配问题

描述：某厂根据计划安排，拟将n 台相同的设备分配给m 个车间，各车间获得这种设备后，可以为国家提供盈利Cij(j 台设备提供给i 号车间将得到的利润，1≤i≤m，1≤j≤n) 。问如何分配，才使国家得到最大的盈利？

 

算法基本思路：

1.求最大利润

输入：c[i][j] = 将 j+1 台设备分配给 i+1 号车间得到的利润。

定义：将 j 台设备分配给前 i 个车间的最大利润 p[i][j]（即题目所求的是p[m][n]），因此p[i][j]是以下两种情况的较大值：

(1)不分配给 i 号车间，此时的最大值为将j 台设备分配给前 i-1 个车间的最大值，p[i][j] = p[i-1][j]；

(2)分配 k 台设备给 i 号车间，剩下的 j-k 台设备分配给前 i-1 个车间，此时p[i][j] = c[i-1][k-1] + p[i-1][j-k]，其中 1≤ k ≤j。

即 p[i][j] = max{p[i-1][j], c[i-1][k-1] + p[i-1][j-k]}，其中1≤ k ≤j.

 

初始化p[0][j] = 0（将 j 台设备分配给前 0 个车间），p[i][0] = 0（将 0 台设备分配给前 i 个车间）。

从i = 0 开始自底向上构造表即可计算出 p[m][n].

 

 

2.求设备分配给哪些车间以及其分配数量。

在1.的基础上，在求p[i][j]的过程中，以表 l[i][j] 表示分配给 i 号车间的设备数。

 

从 i = m, j = n 开始逆推，

若 l[i][j] = 0，则表示这个车间没有分配到设备，此时 i --；

若 l[i][j] = 某个数k, 则表示这个车间分配到 k 台设备，此时 i --, j -= k。

 

代码实现细节：

算法里面的 m 和 n 与上面说的有点不一样，实质上是m+1 和 n+1，只是为了写的时候方便，注意区分。

import java.util.Arrays;

public class ResourceAllocation{

    public static String maxProfit(int[][] c){
        /*
        c[i][j] means the profit (j+1) devices are assigned to allocation (i+1)
        note that the index of c begins with 0
        
        p[i][j] means the max profit of j devices are assigned to allocations(1,2,...,i)
        p[i][j] = max{p[i-1][j], c[i-1][k-1] + p[i-1][j-k]}(1<= k <=j)
        
        l[i][j] means the number of devices are assigned to allocation i
        */
        int m = c.length+1, n = c[0].length+1;
        int[][] p = new int[m][n];
        int[][] l = new int[m][n];
        //init
        for(int i = 0; i < m; i ++)
            p[i][0] = 0;
        for(int j = 0; j < n; j ++)
            p[0][j] = 0;
        //dynamic programming
        for(int i = 1; i < m; i ++){
            for(int j = 1; j < n; j ++){
                int max = p[i-1][j];
                l[i][j] = 0;
                for(int k = 1; k <= j; k ++){
                    if(max < c[i-1][k-1] + p[i-1][j-k]){
                        max = c[i-1][k-1] + p[i-1][j-k];
                        l[i][j] = k;
                    }
                }
                p[i][j] = max;
            }
        }
        //build path
        String result = "";
        for(int i = m-1, j = n-1; i > 0 && j > 0;){
            if(l[i][j] == 0)
                i --;
            else{
                result = "\n" + "workshop" + i + " assign: " + l[i][j] + result;
                j -= l[i][j];
                i --;
            }
        }
        result = "max profit: " + p[m-1][n-1] + result;
        return result;
    }

    public static void main(String[] args) {
        int[][] c = new int[3][10];
        for(int i = 0; i < 3; i ++){
            c[i][0] = (int)(Math.random()*10);
            for(int j = 1; j < 10; j ++){
                c[i][j] = c[i][j-1] + (int)(Math.random()*5);
            }
        }
        for(int i = 0; i < 3; i ++)
            System.out.println(Arrays.toString(c[i]));
        System.out.println(maxProfit(c));
    }
    
}