Diving Board
16.11 Diving Board: You are building a diving board by placing a bunch of planks of wood end-to-end. There are two types of planks, one of length shorter and one of length longer. You must use exactly K planks of wood. Write a method to generate all possible lengths for the diving board.
- Not the most efficient, but we can build a B-tree that expands out to represent the possible combinations given k planks (building k levels in the process.
- Each node will represent the accumulative length until we get to the leafs. Our final result will be the values of our leafs in the tree.
- The reason this isn't entirely efficient is because we will obtain so overlap in the sum of the values (2+3) = (3+2), but our tree distinct them as different.
- The larger the k, the more overlaps.
- Optimized: With only two possibilities and k levels. The unique combinations made are simple:
- Ex.
len1 = 3, len2 = 4, k = 4- Produces unique sums that are reflected by: its key combination:
- 2222 = 8
- 2223 = 9
- 2233 = 10
- 2333 = 11
- 3333 = 12
vector<int> build_k_planks(int k, int length1, int length2) {
vector<int> comb (k);
vector<vector<int>> combs;
combs.reserve(k + 1);
fill(comb.begin(), comb.end(), length1);
combs.push_back(comb);
// now modify this vector
for (int i = 0; i < k; i++) {
comb[i] = length2;
combs.push_back(comb);
}
comb.clear();
// now return sum
for (auto i : combs) {
int sum = accumulate(i.begin(), i.end(), 0);
comb.push_back(sum);
}
return comb;
}
int main() {
vector<int> sums = build_k_planks(4, 2, 3);
for (auto i : sums) cout << i << " "; cout << endl;
pause();
sums = build_k_planks(10, 45, 21);
for (auto i : sums) cout << i << " "; cout << endl;
pause();
}
Last modified 4yr ago