Knapsacker おやつは500円までコンピュータ

「おやつは５００まで」問題（学術的には組合せ最適化問題 Knapsack Problem）をお買い物の現場で解決できる「今週のアルゴリズム・メカ」１号プロトタイプである．

説明しよう．ダイヤル一つとボタン一つの操作だけで１０アイテムまでお菓子の価格を登録でき，２の１０乗の組合せすべてをあっという間にチェックして，５００円以内でもっとも総額が高くなる組合せをＬＥＤの点滅で教えてくれるのだ．バー型ＬＥＤやブレッドボードサイズの制約で，１０アイテムまでの組合せとなっている．
私は５００円じゃなくて２００円だった？大丈夫．ソフトウェア・アップデートとモード・セレクトスイッチの追加で，２００円など，５００円以外の制限額も利用可能になる（予定）．

二進数で値段を確認するのが苦手な人は，オプションでＬＣＤディスプレイ装置（シリアル接続）が使え，テキストメッセージで入力額，それまでに入力したアイテムの合計金額も出るようになっている．私も苦手だ．
作り方は，画像でわかるとおりだ．
装置は大きくなっていくが，アイテム数を増やすのは簡単だ．Arduino のピン数がたりなくなっても，I2CやSPIを使うI/Oエクスパンダや７セグメントＬＥＤコントローラを使って駆動ＬＥＤ数を増やすことができる．

難しい話まですると，アルゴリズムとその効率を学んでいるなら，部分集合すべてをつくして合計金額を確かめる方法では，１０個ぐらいが限度だと気づくはずだ．１個増えるごとに，計算時間は２倍以上になっていくからだ（O(n 2^n)）．１６個で，すでに数十秒またされることになるだろう．

//Knapsacker.pde

#include 
#include 
#include "SerLCD.h"

SerLCD slcd(19);

const int ItemNumLimit = 10;
int prices[ItemNumLimit];
byte best[ItemNumLimit];

void setup() {
  slcd.begin(9600);

  pinMode(12,INPUT);
  
  for (int ic = 0; ic < ItemNumLimit; ic++) {
    pinMode(0+ic, OUTPUT);
    digitalWrite(0+ic, LOW);
  }
  
  for (int ic = 0; ic < ItemNumLimit; ic++) {
    prices[ic] = 0;
  }

  slcd.clear();
}

int analog0 = 0;
int itemNo = 0, tally = 0;
boolean clicked = false;
void loop() {
  int bestPrice;
  
  showBinary(analog0);
  if (digitalRead(12) == LOW && !clicked) {
    clicked = true;
    //
    prices[itemNo] = analog0;
    tally += prices[itemNo];
    itemNo++;
    for (int ic = 0; ic < 2; ic++) {
      showBinary(0);
      slcd.noDisplay();
      delay(250);
      showBinary(analog0);
      slcd.display();
      delay(250);
    }
  } else if (digitalRead(12) == HIGH && clicked) {
    clicked = false;
  }
  
  if (itemNo >= ItemNumLimit ) {
    slcd.clear();
    for (int ic = 0; ic < ItemNumLimit && prices[ic] != 0; ic++) {
      
      slcd.setCursor(0,1);
      slcd.print("#");
      slcd.print(1+ic);
      slcd.print(" ");
      slcd.print(prices[ic]);
      
      showBinary(0);
      delay(100);
      showBinary(prices[ic]);
      delay(500);
    }
    bestPrice = computeBest(prices, best);
    showBinary(best);
    slcd.clear();
    slcd.print("Buy ");
    slcd.setCursor(0,1);
    slcd.print("Total ");
    slcd.print(bestPrice);
    for (int ic = 0; ic < 2; ic++) {
      delay(500);
      slcd.noDisplay();
      delay(500);
      slcd.display();
    }
    while (digitalRead(12) == HIGH);
    for (int ic = 0; ic < ItemNumLimit; ic++) {
      prices[ic]= 0;
    }
    itemNo = 0;
    tally = 0;
  }
  
  analog0 = (analog0 + (analogRead(0)>>1))>>1;

  slcd.home();  
  slcd.print("#");
  slcd.print(1+itemNo);
  slcd.print(" Price ");
  slcd.print(analog0);
  slcd.print("  ");
  slcd.setCursor(0,1);
  slcd.print("Total: ");
  slcd.print(tally);
  slcd.print("  ");
  
}

void showBinary(byte b[]) {
  for (int i = 0; i < ItemNumLimit; i++) {
    if ( b[i] != 0)
      digitalWrite(i, HIGH);
    else
      digitalWrite(i, LOW);
  }
}

void showBinary(int v) {
  for (int i = 0; i < ItemNumLimit; i++) {
    if ( (v & 1 << i) != 0)
      digitalWrite(i, HIGH);
    else
      digitalWrite(i, LOW);
  }
}

int computeBest(int value[], byte best[]) {
  int bestPrice = 0, total, i;
  byte buy[ItemNumLimit];

  for (int i = 0; i < ItemNumLimit; i++) {
    buy[i] = 0;
    best[i] = 0;
  }
  while (true) {
    total = 0;
    showBinary(buy);
    for (i = 0; i < ItemNumLimit; i++) {
      if ( buy[i] != 0 ) {
        total += value[i];
      }
    }
    if (total <= 500 && total > bestPrice) {
      bestPrice = total;
      for (int i = 0; i < ItemNumLimit; i++) {
        best[i] = buy[i];
      }
      // the best is updated
      slcd.setCursor(0,1);
      slcd.print("Best Price: ");
      slcd.print(bestPrice);
    }
    // next buying list
    for (i = 0; i < ItemNumLimit; i++) {
      if (buy[i] == 0) {
        buy[i] = 1;
        break;
      } else {
        buy[i] = 0;
      }
    }
    if (i == ItemNumLimit)
      break;
  }
  return bestPrice;
}