> For the complete documentation index, see [llms.txt](https://trizen.gitbook.io/sidef-lang/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://trizen.gitbook.io/sidef-lang/programming_tasks/k/knapsack-problem/0-1.md).

# 0-1

```ruby
var raw = <<'TABLE'
map,                      9, 150
compass,                 13,  35
water,                  153, 200
sandwich,                50, 160
glucose,                 15,  60
tin,                     68,  45
banana,                  27,  60
apple,                   39,  40
cheese,                  23,  30
beer,                    52,  10
suntancream,             11,  70
camera,                  32,  30
T-shirt,                 24,  15
trousers,                48,  10
umbrella,                73,  40
waterproof trousers,     42,  70
waterproof overclothes,  43,  75
note-case,               22,  80
sunglasses,               7,  20
towel,                   18,  12
socks,                    4,  50
book,                    30,  10
TABLE
 
struct KnapsackItem {
    String name,
    Number weight,
    Number value,
}
 
var items = []
raw.each_line{ |row|
    var fields = row.split(/\s*,\s*/)
    items << KnapsackItem(
          name: fields[0],
        weight: fields[1].to_n,
         value: fields[2].to_n,
    )
}
 
var max_weight = 400
var p = [
    items.len.of { [[0, []], max_weight.of(nil)...] }...,
    max_weight.inc.of {[0, []]}
]
 
func optimal(i, w) {
    if (!defined p[i][w]) {
        var item = items[i];
        if (item.weight > w) {
            p[i][w] = optimal(i.dec, w)
        }
        else {
            var x = optimal(i.dec, w)
            var y = optimal(i.dec, w - item.weight)
 
            if (x[0] > (y[0] + item.value)) {
                p[i][w] = x;
            }
            else {
                p[i][w] = [y[0] + item.value, [y[1]..., item.name]]
            }
        }
    }
    return p[i][w]
}
 
var sol = optimal(items.end, max_weight)
say "#{sol[0]}: #{sol[1].join(' ')}"
```

#### Output:

```
1030: map compass water sandwich glucose banana suntancream waterproof trousers waterproof overclothes note-case sunglasses socks
```