どのコインをつかうか問題を貪欲法で解をだしてみるiPhoneアプリのサンプルコードを描いてみます。
#import “ViewController.h”
#include <memory>
using namespace std;
struct Coins {
int c1;
int c5;
int c10;
int c50;
};
typedef struct Coins Coins;
class CoinProblemSolver {
public:
Coins solveByGreed(int, Coins);
};
Coins CoinProblemSolver::solveByGreed(int targetPrice, Coins coinsOnHand) {
int selectCoins[] = {0,0,0,0};
int key[] = {1, 5, 10, 50};
int onhand[] = {coinsOnHand.c1, coinsOnHand.c5, coinsOnHand.c10, coinsOnHand.c50};
int idx = 3;
// check! bigger -> small (50, 10, 5, 1)
while (idx > –1 && targetPrice > 0) {
if (key[idx] > targetPrice || onhand[idx] == 0) {
idx–;
continue;
}
selectCoins[idx]++;
onhand[idx]–;
targetPrice -= key[idx];
}
return Coins{selectCoins[0], selectCoins[1], selectCoins[2], selectCoins[3]};
};
@interface ViewController () {
Coins yourCoins;
}
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
[self setupPriceAndCoins];
[self createTray];
}
– (void)setupPriceAndCoins {
int targetPrice = 123;
UILabel *target = [[UILabel alloc] init];
target.text = [NSString stringWithFormat:@”price : %d”, targetPrice];
target.font = [UIFont boldSystemFontOfSize:50];
[target sizeToFit];
target.center = CGPointMake(CGRectGetMidX(self.view.bounds), 120);
[self.view addSubview:target];
// set your coins
yourCoins = {4, 1, 3, 2};
NSDictionary *coins = @{@”50″: @(yourCoins.c50), @”10″: @(yourCoins.c10), @”5″: @(yourCoins.c5), @”1″: @(yourCoins.c1)};
__block int count = 0;
[coins enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
for (int i=0; i<[obj intValue]; i++) {
UIView *c = [self coin:[key intValue]];
float x = (count % 5) * 50 + 80;
float y = (count / 5) * 50 + 320;
c.center = CGPointMake(x, y);
[self.view addSubview:c];
count++;
}
}];
}
– (UIView *)coin:(int)price {
UIView *coin = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 40, 40)];
coin.tag = price;
coin.backgroundColor = [UIColor lightGrayColor];
coin.layer.cornerRadius = 20;
UILabel *priceLabel = [[UILabel alloc] init];
priceLabel.text = [NSString stringWithFormat:@”%d”, price];
priceLabel.font = [UIFont boldSystemFontOfSize:15];
[priceLabel sizeToFit];
priceLabel.center = CGPointMake(20, 20);
[coin addSubview:priceLabel];
return coin;
}
– (void)createTray {
UIView *tray = [[UIView alloc] initWithFrame:CGRectMake(20, 150, CGRectGetMaxX(self.view.bounds) – 40, 130)];
tray.backgroundColor = [UIColor clearColor];
tray.layer.borderColor = [UIColor lightGrayColor].CGColor;
tray.layer.borderWidth = 2;
tray.layer.cornerRadius = 5;
[self.view addSubview:tray];
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event
{
shared_ptr<CoinProblemSolver> cppClass(new CoinProblemSolver());
__block Coins ans = cppClass->solveByGreed(123, yourCoins);
__block int counter = 0;
NSSortDescriptor *sort = [NSSortDescriptor sortDescriptorWithKey:@”tag” ascending:NO];
[[self.view.subviews sortedArrayUsingDescriptors:@[sort]] enumerateObjectsUsingBlock:^(UIView *v, NSUInteger idx, BOOL *stop) {
BOOL useit = NO;
if (v.tag == 1 && ans.c1 > 0) {
ans.c1 = ans.c1 – 1;
useit = YES;
}
else if (v.tag == 5 && ans.c5 > 0) {
ans.c5 = ans.c5 – 1;
useit = YES;
}
else if (v.tag == 10 && ans.c10 > 0) {
ans.c10 = ans.c10 – 1;
useit = YES;
}
else if (v.tag == 50 && ans.c50 > 0) {
ans.c50 = ans.c50 – 1;
useit = YES;
}
if (useit) {
v.tag = 0;
float x = (counter % 5) * 50 + 80;
float y = (counter / 5) * 50 + 200;
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(0.5 * counter * NSEC_PER_SEC)), dispatch_get_main_queue(), ^{
[UIView animateWithDuration:0.5 animations:^{
v.center = CGPointMake(x, y);
}];
});
counter++;
}
}];
}
@end