dp：投資問題

有8萬元的投資可以投給3個項目，每個項目在不同投資數額下（以萬元為機關）的利潤如下表。

請安排投資計劃，使總的利潤最大。

寫出你所設的狀态變量、決策變量、狀态轉移方程與遞推關系式，和手工求解的詳細步驟及結果。

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

struct best_choice {
    int dp; // 賺的錢
    int index_g; // 目前第k個項目投資額
    int index_f; // 從k+1 ... n所有項目投資額
};
struct best_choice best_choice[3][9] = {0};
int project[3][9] = {{0, 5, 15, 40, 80, 90, 95, 98, 100},
                         {0, 5, 15, 40, 60, 70, 73, 74, 75},
                         {0, 4, 26, 40, 45, 50, 51, 52, 53}};

void show_index(int i, int j) {
    if (i == 2) {
        printf("第%d個項目投資%d萬元\n", i + 1, j);
        return;
    }
    else {
        printf("第%d個項目投資%d萬元\n", i + 1, best_choice[i][j].index_g);
        show_index(i + 1, best_choice[i][j].index_f);
    }
}

int main() {

    int i, j, k;
    int n;
    int temp_max;
    int temp_g;
    int temp_f;
    n = 3;

    for (k = n - 1; k >= 0; k--) {
        if (k == n - 1) {
            for (i = 0; i < 9; i++) {
                best_choice[k][i].dp = project[k][i];
                best_choice[k][i].index_g = k;
                best_choice[k][i].index_f = -1;
            }
        }
        else {
            for (i = 0; i < 9; i++) {
                temp_max = 0;
                temp_g = 0;
                temp_f = 0;
                for (j = 0; j <= i; j++) {
                    if (project[k][j] + best_choice[k + 1][i - j].dp > temp_max) {
                        temp_max = project[k][j] + best_choice[k + 1][i - j].dp;
                        temp_g = j;
                        temp_f = i - j;
                    }
                }
                best_choice[k][i].dp = temp_max;
                best_choice[k][i].index_g = temp_g;
                best_choice[k][i].index_f = temp_f;
            }
        }
    }

    printf("最多能賺%d萬元\n", best_choice[0][8].dp);
    show_index(0, 8);
    puts("");
    printf("dp表格如下\n");
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 8; j++) {
            printf("%-3d ", best_choice[i][j].dp);
        }
        if (j == 8) {
            printf("%-3d\n", best_choice[i][j].dp);
        }
    }
    return 0;
}