package main

import "fmt"

type Item struct {
	name               string
	weight, value, qty int
}

var items = []Item{
	{"map",			9,	150,	1},
	{"compass",		13,	35,	1},
	{"water",		153,	200,	2},
	{"sandwich",		50,	60,	2},
	{"glucose",		15,	60,	2},
	{"tin",			68,	45,	3},
	{"banana",		27,	60,	3},
	{"apple",		39,	40,	3},
	{"cheese",		23,	30,	1},
	{"beer",		52,	10,	3},
	{"suntancream",		11,	70,	1},
	{"camera",		32,	30,	1},
	{"T-shirt",		24,	15,	2},
	{"trousers",		48,	10,	2},
	{"umbrella",		73,	40,	1},
	{"w-trousers",		42,	70,	1},
	{"w-overclothes",	43,	75,	1},
	{"note-case",		22,	80,	1},
	{"sunglasses",		7,      20,	1},
	{"towel",		18,	12,	2},
	{"socks",		4,      50,	1},
	{"book",		30,	10,	2},
}

type Chooser struct {
	Items []Item
	cache map[key]solution
}

type key struct {
	w, p int
}

type solution struct {
	v, w int
	qty  []int
}

func (c Chooser) Choose(limit int) (w, v int, qty []int) {
	c.cache = make(map[key]solution)
	s := c.rchoose(limit, len(c.Items)-1)
	c.cache = nil