[알고리즘] Assignment 4

Implement the following algorithms in the C programming language and put the described input to the algorithm in order to check the answer. Submit 1) a report containing outputs of the following problems and 2) the codes you have written (screenshots okay).

 

1. Implement an algorithm of Fibonacci numbers using dynamic programming and get the answers when feeding 𝑛=5 and 𝑛=10 into the algorithm as inputs (find the 𝑛th number).

[Note that you should store the results we’ve calculated and return the values when needed.]

#include <stdio.h>
#define N1 5
#define N2 10

long long r[100] = { 0,1,1 };
long long fibonacci(int n) {
	long long result = 1;
	if (r[n]) {
		return r[n];
	}
	else {
		long long first = 0;
		long long second = 0;
		first = fibonacci(n - 1);
		second = fibonacci(n - 2);

		r[n] = first + second;
		return r[n];
	}
}

int main()
{
	printf("%d\n", int(fibonacci(N1)));
	printf("%d\n", int(fibonacci(N2)));

	return 0;
}

 

 

2. Implement a matrix-chain multiplication algorithm using dynamic programming and perform the algorithm for a chain of three matrices containing randomly chosen positive integers whose sizes are 5×3, 3×7, and 7×10, respectively (output should be a matrix of size 5×10). Display your output matrix, optimal chain order, and the minimum number of computations.

[Note that you are required to feed a sequence of dimensions of the matrices into the algorithm (i.e., ⟨5,3,7,10⟩).]

#include <stdio.h>
#include <malloc.h>
#define number 3
int dim[number + 1] = { 5,3,7,10 };

void order(int i, int j, int mat[number][number])
{
    int k;
    if (i == j) {
        printf("A%d", i);
    } else {
        k = mat[i][j];
        printf("(");
        order(i, k, mat);
        order(k + 1, j, mat);
        printf(")");
    }
}

int mult(int n, int dim[], int mat[number][number]) 
{
    int i, j, k, dimv, dia, min = 0, temp =0;
    int M[number][number];
    for (i = 1; i <= n; i++)
        M[i][i] = 0;
    for (dia = 1; dia <= n - 1; dia++) {
        for (i = 1; i <= n - dia; i++) {
            j = i + dia;
            for (k = i; k <= j - 1; k++) {
                M[i][j] = M[i][k] + M[k + 1][j];
                dimv = dim[i - 1] * dim[k] * dim[j];
                M[i][j] += dimv;
                if (i == k) {
                    temp = M[i][j];
                    min = k;
                } else if (M[i][j] > temp) {
                    M[i][j] = temp;
                } else {
                    min = k;
                }
            }
            mat[i][j] = min;
        }
    }
    return M[1][n];
}

int main()
{
    int mat[number][number];
    int result = mult(number, dim, mat);
    order(1, number, mat);
    printf("\nMinimum Multiplication is %d\n", result);

    return 0;
}

 

 

3. Implement an algorithm for the fractional knapsack problem by a greedy strategy.

 

A. Assume that we have a knapsack with max weight capacity of 16, and our objective is to fill the knapsack with items such that the benefit (value) is maximum. Consider the following items and their associated weight and value:

ITEM	WEIGHT	VALUE
1	6	60
2	10	20
3	3	12
4	5	80
5	1	30
6	3	60

B. Sort the items in decreasing order of value / weight, and only the last item in the sorted list need to be broken up as in a greedy approach the current item is guaranteed to be the optimum one to take. [Note that the last item denotes an item in the list that makes the knapsack of maximum capacity when filling with (fraction of) the item.]

 

C. Display the maximum value and its associated items (with their fraction numbers) for the problem.

 

#include<stdio.h>
#define MAX 6
#define capacity 16

double weight[MAX] = { 6,10,3,5,1,3 };
double value[MAX] = { 60,20,12,80,30,60 };

int main()
{
	int i, j, item[MAX];
	double ratio[MAX], amount[MAX], temp, total = 0, space = capacity;

	for (i = 0; i < MAX; i++) {
		item[i] = i + 1;
	}

	for (i = 0; i < MAX; i++) {
		ratio[i] = value[i] / weight[i];
	}

	for (i = 0; i < MAX; i++) {
		for (j = i + 1; j < MAX; j++) {
			if (ratio[i] < ratio[j]) {
				temp = ratio[i];
				ratio[i] = ratio[j];
				ratio[j] = temp;

				temp = weight[i];
				weight[i] = weight[j];
				weight[j] = temp;

				temp = value[i];
				value[i] = value[j];
				value[j] = temp;

				temp = item[i];
				item[i] = item[j];
				item[j] = temp;
			}
		}
	}

	for (i = 0; i < MAX; i++) {
		amount[i] = 0.0;
	}

	for (i = 0; i < MAX; i++) {
		if (weight[i] > space) {
			break;
		}
		else {
			amount[i] = 1.0;
			total += value[i];
			space -= weight[i];
		}
	}

	if (i < MAX) {
		amount[i] = space / weight[i];
	}
	
	total += amount[i] * value[i];

	printf("the maximum value : %f\n", total);
	printf("its associated items :\n");

	for (i = 0; i < MAX; i++)
	{
		printf("  ITEM %d: %10f%% \n", item[i], amount[i] * 100.0);
	}

	return 0;
}