> 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/bounded.md).

# Bounded

```ruby
var raw = <<'TABLE'
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      1
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_overcoat   43      75      1
note-case    22      80      1
sunglasses    7      20      1
towel        18      12      2
socks         4      50      1
book         30      10      2
TABLE
 
struct KnapsackItem {
    String name,
    Number weight,
    Number value,
    Number quant,
}
 
var items = []
raw.each_line{ |row|
    var fields = row.words;
    items << KnapsackItem(
          name: fields[0],
        weight: fields[1].to_n,
         value: fields[2].to_n,
         quant: fields[3].to_n,
    )
}
 
func pick(weight, pos) is cached {
 
    if (pos.is_neg || weight.is_neg || weight.is_zero) {
        return (0, 0, [])
    }
 
    var (bv=0, bi=0, bw=0, bp=[])
    var item = items[pos];
 
    for i in range(0, item.quant) {
        break if (i*item.weight > weight)
        var (v, w, p) = pick(weight - i*item.weight, pos.dec)
        next if ((v += i*item.value) <= bv)
        (bv, bi, bw, bp) = (v, i, w, p)
    }
 
    (bv, bw + bi*item.weight, [bp..., bi])
}
 
var (v, w, p) = pick(400, items.end)
p.range.each { |i|
    say "#{p[i]} of #{items[i].name}" if p[i].is_pos
}
say "Value: #{v}; Weight: #{w}"
```

#### Output:

```
1 of map
1 of compass
1 of water
2 of glucose
3 of banana
1 of cheese
1 of suntancream
1 of w_overcoat
1 of note-case
1 of sunglasses
1 of socks
Value: 1010; Weight: 396
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://trizen.gitbook.io/sidef-lang/programming_tasks/k/knapsack-problem/bounded.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.