演算法 Rod Cutting Problem

#include <stdio.h>
#define _CRT_SECIURE_NO_WARNINGS

int main()
{
    int k;
    scanf_s("%d", &k);
    int r[100], s[100], p[100]; // r:最大總價格 s:第一刀的長度

    for (int i = 1; i <= k; i++) {
        scanf_s("%d", &p[i]);
    }
    r[0] = 0;

    for (int j = 1; j <= k; j++) {
        int q = -1;
        for (int i = 1; i <= j; i++) {
            if (q < (p[i] + r[j - i])){
                q = p[i] + r[j - i];
                s[j] = i;
            }
        }
        r[j] = q;
    }
    
    printf("%d\n", r[k]); // 最大總價格

    int index_k = k, cut_total = 1; // cut_total:總共切幾刀
    int cut_index[100], i = 1; // cut_index:每一刀切多長

    if (index_k - s[index_k] == 0)  // 只切一刀
    {
        printf("1\n");
        printf("%d=%d", k, k);
    }
    else 
    {
        cut_total++;
        cut_index[i] = s[index_k];
        i++;
        index_k = index_k - s[index_k];
        while (index_k - s[index_k] != 0) {
            cut_total++;
            cut_index[i] = s[index_k];
            i++;
            index_k = index_k - s[index_k];
        }
        cut_index[i] = s[index_k];

        printf("%d\n", cut_total);
        printf("%d=%d", k, cut_index[1]);
        for (i = 2; i <= cut_total; i++) {
            printf("+%d", cut_index[i]);
        }
    }



}