一维资源分配

1.问题介绍

设有总量为a的某种原料，用于生产n种产品。假设用于生产第k种产品生产的数量为\(x_k\),并获得收益 \(\varphi(x_k)\)，问应该如何分配n种产品的资源使用量使得总收益最大。

2.Solution

\(k\) ：生产第k种产品的决策阶段；
\(x_k\) ：投入到第k种产品生产的资源数；
\(s_k\) ：第k阶段开始时拥有的资源数量，则状态转移方程为 \(s_{k+1}= s_k - x_k\)；
\(\varphi(x_k)\) ：生产第k种产品所获得的收益；
\(f_k(s_k)\) ：从第k种产品开始一直到第n种产品生产完的最大总收益；

\[\begin{cases} f_k(s_k) = MAX_{0≤ x_k ≤ s_k}\left\{\varphi(x_k)+f_{k+1}(s_{k+1})\right\} \\\\ f_{n+1}(s_{n+1}) = 0 \end{cases} \]

3. Example

某企业现有资金 5000 万元准备对 A，B，C三个项目投资。假设对各项目的投资额只能取1000 万元的整数倍，各种情况下的利润 (单位: 万元) 如下表所示。问对三个项目的投资额各为多少时，总利润为最大?

投资额\项目	A	B	C
0	0	0	0
1	40	100	80
2	200	200	180
3	320	300	300
4	400	400	420
5	380	400	420

动态打表

Java实现

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static int N; // 投资额可选数
    static int P; // 项目数
    static int[][] profit; // 某种投资额数下某项目获利
    static int[][] profit_sum; // 某资金总数下只对某一项目采取某投资额的总利润
    static int[][] profit_max; // 存放每一个阶段下每一个资金总数下投资额的最优利润
    static ArrayList<ArrayList<ArrayList<Integer>>> best_X = new ArrayList<>(); // 存放最大利润对应投资额
    static int max; // 算最大利润时用

    public static void main(String[] args) throws IOException {
        // 读取投资额可选数和项目数
        String[] s = in.readLine().split(" ");
        N = Integer.parseInt(s[0]);
        P = Integer.parseInt(s[1]);
        
        profit = new int[N][P];
        profit_sum = new int[N][N];
        
        // 读取每个投资额数下每个项目的利润
        for (int i = 0; i < N; i++) {
            s = in.readLine().split(" ");
            for (int j = 0; j < P; j++)
                profit[i][j] = Integer.parseInt(s[j]);
        }
        
        profit_max = new int[N][N];
        // 调用ko()函数计算最优利润
        ko();
        
        System.out.println("得到最优分配方案：");
        // 递归打印出最优分配方案以及最大利润
        dfs(best_X.get(P-1).get(0), best_X.size()-1, "", N-1);
        System.out.println("最大利润：" + profit_max[0][N-1]);
    }

    private static void ko() {
        for (int k = P - 1; k >= 0; k--) {
            ArrayList<ArrayList<Integer>> pk = new ArrayList<>();
            best_X.add(pk);
            
            if (k == 0) {
                max = Integer.MIN_VALUE;
                // 计算最后一个阶段的投资额的利润和下一阶段资金总数的最优利润之和
                for (int x = 0; x < N; x++) {
                    profit_sum[N-1][x] = profit[x][k] + profit_max[k + 1][N - 1 - x];
                    max = Math.max(max, profit_sum[N-1][x]);
                }
                pk.add(new ArrayList<Integer>());
                for (int x = 0; x < N; x++) {
                    // 将最大利润对应的投资额添加到best_X中
                    if (max == profit_sum[N-1][x]) {
                        pk.get(0).add(x);
                    }
                }
                profit_max[k][N-1] = max;
            } else {
                for (int S = 0; S < N; S++) {
                    max = Integer.MIN_VALUE;
                    // 计算当前阶段下每个资金总数对应的投资额的总利润
                    for (int x = 0; x <= S; x++) {
                        profit_sum[S][x] = (k == P-1 ? profit[x][k] : (profit[x][k] + profit_max[k + 1][S - x]));
                        max = Math.max(max, profit_sum[S][x]);
                    }
                    // 将每个资金总数对应的最大利润的投资额添加到best_X中
                    addbest_x(max, S, pk);
                    profit_max[k][S] = max;
                }
            }
        }
    }

    private static void dfs(ArrayList<Integer> index_best, int flag, String res, int S) {
        if (flag == 0) {
            for (int index : index_best) {
                // 将找到的最优分配方案打印出来
                if (S - index == 0)
                    System.out.println("---> " + res + index);
            }
            return;
        }
        // 递归查找下一个阶段的最优分配方案
        for (int index : index_best) {
            dfs(best_X.get(flag - 1).get(S - index), flag - 1, res + index + " + ", S - index);
	}
   }
    private static void addbest_x(int max, int S, ArrayList<ArrayList<Integer>> pk) {
    pk.add(new ArrayList<Integer>());
    for (int x = 0; x < N; x++) {
        // 将最大利润对应的投资额添加到pk中
        if (max == profit_sum[S][x]) {
            pk.get(S).add(x);
        }
    }
   }
}