2009年11月8日日曜日

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

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

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

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

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


//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;
}

0 件のコメント:

コメントを投稿