01ナップサック問題を解いてみるiPhoneアプリ(C++14)のサンプルコードを描いてみます。
#import “ViewController.h”
#include <memory>
#include <functional>
#include <algorithm>
using namespace std;
#define MYMAX 100
class KnapsackSolver {
public:
int solve(int, int, NSArray *weights, NSArray *values);
};
int KnapsackSolver::solve(int n, int capacity, NSArray *weights, NSArray *values) {
int w[MYMAX];
int v[MYMAX];
int dp[MYMAX][MYMAX];
for (int i=0; i<weights.count; i++) {
w[i] = [weights[i] intValue];
v[i] = [values[i] intValue];
}
memset(dp, –1, sizeof(dp));
function<int(int, int)> f = [&, w=w, v=v, n=n, dp=dp](int i , int j) {
if (dp[i][j] >= 0)
return dp[i][j];
int res;
if (i == n)
res = 0;
else if (j < w[i])
res = f(i + 1, j);
else
res = max(f(i + 1, j), f(i + 1, j – w[i]) + v[i]);
return dp[i][j] = res;
};
return f(0, capacity);
}
@interface ViewController ()
@property (nonatomic, strong) NSArray *weights;
@property (nonatomic, strong) NSArray *values;
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
self.view.backgroundColor = [UIColor colorWithHue:0.6 saturation:0.1 brightness:1 alpha:1];
[self createItems];
[self createKnapsack];
}
– (void)createItems {
self.weights = @[@1, @2, @3, @4, @5, @6];
self.values = @[@110, @20, @80, @40, @150, @60];
for(int i=0; i<6; i++) {
float x = (i % 2) * 120 + 120;
float y = (i / 2) * 60 + 120;
UIView *box = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 80, 40)];
box.backgroundColor = [UIColor colorWithHue:0.25 saturation:0.3 brightness:1 alpha:1];
box.center = CGPointMake(x, y);
[self.view addSubview:box];
UILabel *l = [[UILabel alloc] init];
l.text = [self.weights[i] stringValue];
l.font = [UIFont boldSystemFontOfSize:30];
[l sizeToFit];
l.center = CGPointMake(20, 15);
[box addSubview:l];
UILabel *l2 = [[UILabel alloc] init];
l2.text = [self.values[i] stringValue];
[l2 sizeToFit];
l2.center = CGPointMake(60, 20);
[box addSubview:l2];
}
}
– (void)createKnapsack {
UILabel *problem = [[UILabel alloc] init];
problem.font = [UIFont systemFontOfSize:25];
problem.text = @”Knapsack capacity < 10″;
[problem sizeToFit];
problem.center = CGPointMake(CGRectGetMidX(self.view.bounds), 300);
[self.view addSubview:problem];
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
shared_ptr<KnapsackSolver> cppClass(new KnapsackSolver());
int answer = cppClass->solve(6, 10, self.weights, self.values);
UILabel *l = [[UILabel alloc] init];
l.text = [NSString stringWithFormat:@”Ans. %d”, answer];
l.font = [UIFont systemFontOfSize:50];
[l sizeToFit];
l.center = CGPointMake(-CGRectGetMidX(self.view.bounds), 350);
[self.view addSubview:l];
[UIView animateWithDuration:1.0 animations:^{
l.center = CGPointMake(CGRectGetMidX(self.view.bounds), 350);
}];
}
@end