Question

I've only been studying computer science for a few weeks, so I apologize if this is a silly or naive question.

Suppose we're trying to list all elements of the set $$C(r) = \{(x,y,z) \in \mathbb{N}^3 : \sqrt{x^2+y^2+z^2} \leq r\}.$$

An obvious approach would be this: first, list all integers between $0$ and $r$; these become our $x$-values. Then, for each $x$-value, list all integers between $0$ and $\sqrt{r^2-x^2}.$ These become our $y$ values. Then, for each $(x,y)$ pair, list all integers between $0$ and $\sqrt{r^2-x^2-y^2}$. These become our $z$ values. We can visualize this process as a tree; the branches of the tree are the elements of $C(r)$.

A similar approach can be applied to solve the Knapsack problem a little quicker than brute force. Begin by forgetting the value of each item and just focusing on its weight. Now go through the items from left to right, bifurcating each node into two as you go, so that one edge corresponds to "take the item" and the other corresponds to "don't take the item." If taking the item would send you overweight, you refrain from adjoining the edge that corresponds to taking the item, but you still adjoin the one corresponding to not taking the item. In the end, we get a binary tree whose branches can be viewed as subsets of the set of items, which ultimately means fewer numbers that need comparing.

Well, I can see my computer running out of memory pretty quickly trying to do this - I'm sure there's better approaches out there - but nonetheless, if there's a name for this kind of thing, I'd like to know it.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top