ナップサック問題の再帰を用いた実装

C

1#include <stdio.h>2#include <stdlib.h>3#include <time.h>4 5#define max(a, b) (a > b? a: b)6 7/** 8 * ナップサック問題の最適解を探索（動的計画法を用いない） 9 * v: 価格の配列 10 * w: 重さの配列 11 * k: 対象とする荷物の数 12 * i: ナップサックの容量 13 */14int knapsack(int v[], int w[], int k, int i) {15 if (k == 0) return 0;16 17 if (i == 0) return 0;18 19 // 重さが荷物の容量を超える場合、荷物は選べない20 if (w[k] > i) {21 return knapsack(v, w, k-1, i);22 }23 24 // 荷物を選ばない場合と選ぶ場合の価値の最大値を計算25 return max(26 knapsack(v, w, k-1, i), // 荷物を選ばない場合27 knapsack(v, w, k-1, i - w[k]) + v[k] // 荷物を選ぶ場合28 );29}30 31 32int main(int argc, char** argv) {33 /* 教科書：表 6.1の例 34 [1]〜v[4]：価格 35 w[1]〜w[4]：重さ */36 int v[] = {0, 250, 380, 420, 520};37 int w[] = {0, 1, 2, 4, 3};38 39 // 引数処理40 if (argc == 3) {41 int k = atoi(argv[1]);42 int i = atoi(argv[2]);43 if (k < 1 || 4 < k) {44 fprintf(stderr, "kは[1, 4]の範囲で指定してください。");45 return 1;46 }47 printf("結果：%d\n", knapsack(v, w, k, i));48 } else if (argc == 2) {49 // 荷物をランダムに生成50 int n = atoi(argv[1]);51 int* v = (int*)malloc(sizeof(int) * (n + 1));52 int* w = (int*)malloc(sizeof(int) * (n + 1));53 // 乱数の初期化54 srand((unsigned int)time(NULL));55 for (int i = 1; i <= n; i++) {56 v[i] = rand() % 101;57 w[i] = rand() % 10 + 1;58 }59 printf("容量：%d\n", n * 5);60 // 実行時間を計測61 struct timespec start_time, end_time;62 clock_gettime(CLOCK_MONOTONIC, &start_time); // 開始時間を取得63 int i = knapsack(v, w, n, n * 5); // 処理64 clock_gettime(CLOCK_MONOTONIC, &end_time); // 終了時間を取得65 66 // 実行時間の計算67 double execution_time = (double)(end_time.tv_sec - start_time.tv_sec) + (double)(end_time.tv_nsec - start_time.tv_nsec) / 1e9;68 printf("結果：%d\n", i);69 printf("実行時間：%f sec.\n", execution_time);70 free(v);71 free(w);72 } else {73 fprintf(stderr, "Usage: knapsack <k: no. of items> [<i: capacity>]\n");74 return 1;75 }76 return 0;77}