## C# || Counting Bits – How To Return The Number Of 1’s In Binary Representation Of X Using C#

The following is a module with functions which demonstrates how to return the number of 1’s in binary representation of X using C#.

1. Count Bits – Problem Statement

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1‘s in the binary representation of i.

Example 1:

``` Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 ```

Example 2:

``` Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101 ```

2. Count Bits – Solution

The following is a solution which demonstrates how return the number of 1’s in binary representation of X.

In this problem, we can see a pattern start to form.

When the current n is even, we can get the answer by dividing by 2 (e.g result[n] = result[n / 2])

When the current n is odd, we can get the answer by getting the result at previous index and adding 1 (e.g result[n] = result[n – 1] + 1)

``` 2. Level Order - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Oct 2, 2022 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to return binary representation of X // ============================================================================ public class Solution { public int[] CountBits(int n) { var result = new int[n + 1]; result[0] = 0; for (int index = 1; index < result.Length; ++index) { if (index % 2 == 0) { result[index] = result[index / 2]; } else { result[index] = result[index - 1] + 1; } } return result; } }// http://programmingnotes.org/ 12345678910111213141516171819202122 // ============================================================================//    Author: Kenneth Perkins//    Date:   Oct 2, 2022//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to return binary representation of X// ============================================================================public class Solution {    public int[] CountBits(int n) {        var result = new int[n + 1];        result[0] = 0;         for (int index = 1; index < result.Length; ++index) {            if (index % 2 == 0) {                result[index] = result[index / 2];            } else {                result[index] = result[index - 1] + 1;            }        }        return result;    }}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

``` [0,1,1] [0,1,1,2,1,2] ```

## C# || How To Find The Largest Divisible Subset In Array Using C#

The following is a module with functions which demonstrates how to find the largest divisible subset in an array using C#.

1. Largest Divisible Subset – Problem Statement

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

• answer[i] % answer[j] == 0, or

If there are multiple solutions, return any of them.

Example 1:

``` Input: nums = [1,2,3] Output: [1,2] Explanation: [1,3] is also accepted. ```

Example 2:

``` Input: nums = [1,2,4,8] Output: [1,2,4,8] ```

2. Largest Divisible Subset – Solution

The following is a solution which demonstrates how to find the largest divisible subset in an array.

This solution uses Dynamic Programming to find the largest divisible subset.

``` 2. Largest Divisible Subset - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Nov 14, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find the largest divisible subset // ============================================================================ public class Solution { public IList<int> LargestDivisibleSubset(int[] nums) { // Sort the array Array.Sort(nums); // List array of size n var dp = new List<int>[nums.Length]; // Go through numbers var resultIndex = 0; for (int i = 0; i < nums.Length; ++i) { dp[i] = new List<int>(); // Go through numbers that come before i and determine the maximum subset for i var currentMaxIndex = i; for (int j = 0; j < i; ++j) { // Check if the two numbers satisfies the condition if ((nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0) && dp[currentMaxIndex].Count < dp[j].Count) { currentMaxIndex = j; } } // Save items from max index to current dp index if (currentMaxIndex != i) { dp[i] = new List<int>(dp[currentMaxIndex]); } // Add current number to current dp index dp[i].Add(nums[i]); // Keep track of the largest subset if (dp[i].Count > dp[resultIndex].Count) { resultIndex = i; } } return dp[resultIndex]; } }// http://programmingnotes.org/ 1234567891011121314151617181920212223242526272829303132333435363738394041424344 // ============================================================================//    Author: Kenneth Perkins//    Date:   Nov 14, 2021//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to find the largest divisible subset// ============================================================================public class Solution {    public IList<int> LargestDivisibleSubset(int[] nums) {        // Sort the array        Array.Sort(nums);         // List array of size n        var dp = new List<int>[nums.Length];         // Go through numbers        var resultIndex = 0;        for (int i = 0; i < nums.Length; ++i) {            dp[i] = new List<int>();             // Go through numbers that come before i and determine the maximum subset for i            var currentMaxIndex = i;            for (int j = 0; j < i; ++j) {                // Check if the two numbers satisfies the condition                if ((nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0) && dp[currentMaxIndex].Count < dp[j].Count) {                    currentMaxIndex = j;                }            }            // Save items from max index to current dp index            if (currentMaxIndex != i) {                dp[i] = new List<int>(dp[currentMaxIndex]);            }             // Add current number to current dp index            dp[i].Add(nums[i]);             // Keep track of the largest subset            if (dp[i].Count > dp[resultIndex].Count) {                resultIndex = i;            }        }        return dp[resultIndex];    }}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

``` [1,2] [1,2,4,8] ```

## C# || How To Find Longest Arithmetic Subsequence Of An Array Using C#

The following is a module with functions which demonstrates how to find the longest arithmetic subsequence of an array using C#.

1. Longest Arithmetic Subsequence Length – Problem Statement

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Recall that a subsequence of an array nums is a list nums[i1], nums[i2], …, nums[ik] with 0 <= i1 < i2 < … < ik <= nums.length – 1, and that a sequence seq is arithmetic if seq[i+1] – seq[i] are all the same value (for 0 <= i < seq.length – 1).

Example 1:

``` Input: nums = [3,6,9,12] Output: 4 Explanation: The whole array is an arithmetic sequence with steps of length = 3. ```

Example 2:

``` Input: nums = [9,4,7,2,10] Output: 3 Explanation: The longest arithmetic subsequence is [4,7,10]. ```

Example 3:

``` Input: nums = [20,1,15,3,10,5,8] Output: 4 Explanation: The longest arithmetic subsequence is [20,15,10,5]. ```

2. Longest Arithmetic Subsequence Length – Solution

The following is a solution which demonstrates how to find the longest arithmetic subsequence of an array.

The main idea in this solution is to maintain a dictionary map array of the differences seen at each index, where dp[index][diff] holds the frequency count at that index, for that specific diff.

Each item in the array is considered and checked against to their items to the left.

For each number (i,j) we determine the difference d = nums[i] – nums[j] and keep a count of the frequency the difference has been seen.

In the end, the max difference frequency is returned.

``` 2. Longest Arithmetic Subsequence Length - Solution C# // ============================================================================ // Author: Kenneth Perkins // Date: Oct 22, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find longest arithmetic subsequence // ============================================================================ public class Solution { public int LongestArithSeqLength(int[] nums) { var result = 0; // Create a map array of size n var dp = new Dictionary<int, int>[nums.Length]; // Iterate the numbers in the array for (int i = 0; i < nums.Length; ++i) { // Create a new dictionary for this index dp[i] = new Dictionary<int, int>(); // Iterate over values to the left of i for (int j = 0; j < i; ++j) { // Get the difference between the two numbers var currentDiff = nums[i] - nums[j]; // Update the count matching the difference already seen from j for i dp[i][currentDiff] = (dp[j].ContainsKey(currentDiff) ? dp[j][currentDiff] : 0) + 1; // Keep track of the max difference count result = Math.Max(result, dp[i][currentDiff]); } } return result + 1; } }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536 // ============================================================================//    Author: Kenneth Perkins//    Date:   Oct 22, 2021//    Taken From: http://programmingnotes.org///    File:  Solution.cs//    Description: Demonstrates how to find longest arithmetic subsequence// ============================================================================public class Solution {    public int LongestArithSeqLength(int[] nums) {        var result = 0;         // Create a map array of size n        var dp = new Dictionary<int, int>[nums.Length];         // Iterate the numbers in the array        for (int i = 0; i < nums.Length; ++i) {             // Create a new dictionary for this index            dp[i] = new Dictionary<int, int>();             // Iterate over values to the left of i            for (int j = 0; j < i; ++j) {                // Get the difference between the two numbers                var currentDiff = nums[i] - nums[j];                 // Update the count matching the difference already seen from j for i                dp[i][currentDiff] = (dp[j].ContainsKey(currentDiff) ? dp[j][currentDiff] : 0) + 1;                 // Keep track of the max difference count                result = Math.Max(result, dp[i][currentDiff]);            }        }         return result + 1;    }}// http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

``` 4 3 4 ```

## C++ || Knapsack Problem Using Dynamic Programming

The following is another homework assignment which was presented in an Algorithm Engineering class. Using a custom timer class, the following is a program which reduces the problem of selecting which Debian Linux packages to include on installation media, to the classical knapsack problem.

The program demonstrated on this page extends the previously implemented Exhaustive Search algorithm, this time using Dynamic Programming to find a solution to this problem.

Debian Package Overview SelectShow

==== 1. THE PROBLEM ====

The Exhaustive Search algorithm ran in O(2n) time and was very slow.

The goal of this program is to implement a dynamic programming algorithm which runs in O(n2 • W) time, returning the optimal set of items/packages contained in the input file, which is fast enough to produce solutions to inputs of realistic size.

This program solves the following problem:

Input: A list of Debian packages, each with a size (in kilobytes) and number of votes, both of which are integers; and an integer `W` representing the capacity of the install media (in kilobytes).

Output: The set of packages with total size `≤ W` , such that the total number of package votes is maximized.

In terms of the knapsack problem, the Debian package votes correspond to knapsack values, and our Debian package sizes correspond to knapsack weights.

==== 2. THE INPUT ====

The following file (knapsack_packages.txt) contains the name, size, and votes for approximately 36,000 binary Debian packages that are currently available on the amd64 platform, and have popcon information.

The file obeys the following format:

```[ number of packages ] [ name 0 ] [ space ] [ votes 0 ] [ space ] [ size 0 ] [ newline ] [ name 1 ] [ space ] [ votes 1 ] [ space ] [ size 1 ] [ newline ] [ name 2 ] [ space ] [ votes 2 ] [ space ] [ size 2 ] [ newline ] ... ```

The packages are arranged within the file in sorted order, from the largest number of votes to the smallest.

==== 3. FLOW OF CONTROL ====

A test harness program is created which executes the above function and measures the elapsed time of the code corresponding to the algorithm in question. The test program will perform the following steps:

`1. Load the "knapsack_packages.txt" file into memory.`

``` 2. Input size "n" and weight "W" as variables. 3. Execute the dynamic knapsack algorithm. The output of this algorithm should be the best combination sequence of packages. ```

```4. Print the first 20 packages from the solution. A solution is the best sequence of packages, displaying the name of the package, the votes, and the size of each package, as well as the total votes and total size of the entire solution. ```

A knapsack problem instances is created of varying input sizes “n” by using the first “n” entries in the file knapsack_packages.txt. In other words, to create a problem instance with `n = 100`, only use the first 100 packages listed in the file as input.

==== 4. TEST HARNESS ====

Note: This program uses two external header files (Timer.h and Project2.h).
• Code for the Timer class (Timer.h) can be found here.
• Code for “Project2.h” can be found here.
• “Project5.h” is listed below.

``` Dynamic Knapsack Test Harness C++ // ============================================================================= // Author: K Perkins // Date: Nov 3, 2013 // Taken From: http://programmingnotes.org/ // File: main.cpp // Description: This is the test harness program which runs the code and // measures the elapsed time of the code corresponding to the algorithm // in question. // // This test program will reduce the problem of selecting which Debian // Linux packages to include on installation media, using the knapsack // problem. The goal is to implement a dynamic programming algorithm // for the knapsack problem, returning an optimal set of items/packages // which is fast enough to produce solutions to inputs of realistic size. // ============================================================================= #include <iostream> #include <cstdlib> #include <cassert> #include <fstream> #include <vector> #include "Timer.h" #include "Project2.h" #include "Project5.h" using namespace std; // the maximum weight const int MAX_WEIGHT = 65536; // the number of packages to examine const int NUM_PACKAGES = 36149; int main() { // declare variables Timer timer; Project5 proj5; Project2 proj2; PackageStats access; ifstream infile; vector<PackageStats> packages; vector<PackageStats> bestCombo; vector<int> knapResult; int* packageWeight = new int[NUM_PACKAGES]; int* packageVotes = new int[NUM_PACKAGES]; int totPackages = 0; // open file & make sure it exists infile.open("knapsack_packages.txt"); if(infile.fail()) { cout<<"nCant find file!n"; exit(1); } // get the total number of packages from the file infile >> totPackages; // make sure there are enough packages in the file assert(NUM_PACKAGES <= totPackages); // get the remaining info from the file // std::string int int for(int x=0;(infile >> access.name >> access.votes >> access.size) && x < NUM_PACKAGES; ++x) { packages.push_back(access); packageWeight[x] = access.size; packageVotes[x] = access.votes; } infile.close(); // display stats cerr<<"n = "<<NUM_PACKAGES<<", W = "<<MAX_WEIGHT <<"nn-- Dynamic Search Solution --n"; // start the timer timer.Start(); // return a vector containing the array indexes // of the best knapsack package solution knapResult = proj5.DynamicKnapsack(packageWeight, packageVotes, NUM_PACKAGES, MAX_WEIGHT); // stop the timer timer.Stop(); // using the data found from above, return // the packages that reside in those array indexes bestCombo = proj5.ReturnBest(packages, knapResult); // display info to the screen cout<<"n- Number of packages generated in this set: "<<bestCombo.size() <<"nn- First 20 packages..nn"; // display the best solution packages proj2.Display(bestCombo, 20); // display the size and total votes cout<<"nTotal Size = "<<proj2.TotalSize(bestCombo)<<" -- Total Votes = " <<proj2.TotalVotes(bestCombo)<<endl; // display the elapsed time cout<<endl<<"It took "<<timer.Elapsed()*1000 <<" clicks ("<<timer.Elapsed()<<" seconds)"<<endl; delete[] packageWeight; delete[] packageVotes; return 0; }// http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108 // =============================================================================//    Author: K Perkins//    Date:   Nov 3, 2013//    Taken From: http://programmingnotes.org///    File:  main.cpp//    Description: This is the test harness program which runs the code and //       measures the elapsed time of the code corresponding to the algorithm //       in question. ////       This test program will reduce the problem of selecting which Debian//       Linux packages to include on installation media, using the knapsack//       problem. The goal is to implement a dynamic programming algorithm//       for the knapsack problem, returning an optimal set of items/packages//       which is fast enough to produce solutions to inputs of realistic size.// =============================================================================#include <iostream>#include <cstdlib>#include <cassert>#include <fstream>#include <vector>#include "Timer.h"#include "Project2.h"#include "Project5.h"using namespace std; // the maximum weightconst int MAX_WEIGHT = 65536; // the number of packages to examineconst int NUM_PACKAGES = 36149; int main(){ // declare variables Timer timer; Project5 proj5; Project2 proj2; PackageStats access; ifstream infile; vector<PackageStats> packages; vector<PackageStats> bestCombo; vector<int> knapResult; int* packageWeight = new int[NUM_PACKAGES]; int* packageVotes = new int[NUM_PACKAGES]; int totPackages = 0;  // open file & make sure it exists infile.open("knapsack_packages.txt"); if(infile.fail()) { cout<<"nCant find file!n"; exit(1); }  // get the total number of packages from the file infile >> totPackages; // make sure there are enough packages in the file assert(NUM_PACKAGES <= totPackages);     // get the remaining info from the file //                      std::string        int             int     for(int x=0;(infile >> access.name >> access.votes >> access.size) && x < NUM_PACKAGES; ++x) { packages.push_back(access); packageWeight[x] = access.size; packageVotes[x] = access.votes; } infile.close(); // display stats cerr<<"n = "<<NUM_PACKAGES<<", W = "<<MAX_WEIGHT <<"nn-- Dynamic Search Solution --n";  // start the timer timer.Start(); // return a vector containing the array indexes // of the best knapsack package solution knapResult = proj5.DynamicKnapsack(packageWeight, packageVotes, NUM_PACKAGES, MAX_WEIGHT); // stop the timer timer.Stop(); // using the data found from above, return // the packages that reside in those array indexes bestCombo = proj5.ReturnBest(packages, knapResult); // display info to the screen cout<<"n- Number of packages generated in this set: "<<bestCombo.size() <<"nn- First 20 packages..nn"; // display the best solution packages proj2.Display(bestCombo, 20); // display the size and total votes cout<<"nTotal Size = "<<proj2.TotalSize(bestCombo)<<" -- Total Votes = " <<proj2.TotalVotes(bestCombo)<<endl;  // display the elapsed time cout<<endl<<"It took "<<timer.Elapsed()*1000 <<" clicks ("<<timer.Elapsed()<<" seconds)"<<endl;  delete[] packageWeight; delete[] packageVotes; return 0;}// http://programmingnotes.org/ ```

==== 5. THE ALGORITHMS – “include Project5.h” ====

``` Knapsack Problem Using Dynamic Programming C++ // ============================================================================= // Author: K Perkins // Date: Nov 3, 2013 // Taken From: http://programmingnotes.org/ // File: Project5.h // Description: This is a simple class which holds the functions for // project 5 // ============================================================================= #ifndef PROJECT5_H #define PROJECT5_H #include <vector> #include <algorithm> #include "Project2.h" using std::vector; struct PackageSet { int index; int weight; vector<int> appearances; }; class Project5 { public: Project5(){} vector<int> DynamicKnapsack(int packageWeight[], int packageVotes[], int numPackages, int maxWeight) { // declare variables vector<int> best; vector<int> temp; vector<PackageSet> pset; int** T = new int*[numPackages+1]; int deleted = 0; int currWeight = maxWeight; bool dontCheck = false; for(int x=0; x <= numPackages; ++x) { T[x] = new int[maxWeight+1]; PackageSet access; dontCheck = false; temp.clear(); for(int y=0; y <= maxWeight; ++y) { if(x==0 || y==0) { T[x][y] = 0; } else if(packageWeight[x-1] <= y) { T[x][y] = std::max(T[x-1][y-packageWeight[x-1]] + packageVotes[x-1], T[x-1][y]); if(T[x][y] == (T[x-1][y-packageWeight[x-1]] + packageVotes[x-1])) { // if we find a valid packet, place it into // the temp vector for storage if(!dontCheck && !(std::find(temp.begin(), temp.end(), packageWeight[x-1]) != temp.end())) { temp.push_back(packageWeight[x-1]); } // find all of the weight instances where // this packet is "valid" access.appearances.push_back(y); dontCheck = true; } } else { T[x][y] = T[x-1][y]; } }// end for loop // gather info about the packet we just found if((std::find(temp.begin(), temp.end(), packageWeight[x-1]) != temp.end())) { access.index = x-1; access.weight = packageWeight[x-1]; pset.push_back(access); } // memory management, used to delete // array indexes thats no longer in use if(x > 1) { delete[] T[deleted++]; } }// end for loop delete[] T; // obtain the best possible knapsack solutuion, and save // their array indexes into a vector, starting from the end // NOTE: this places the knapsack solution in opposite (reverse) order for(int x = pset.size()-1; x >= 0; --x) { if(IsSolution(pset, x, currWeight)) { best.push_back(pset.at(x).index); currWeight -= pset.at(x).weight; } pset.pop_back(); } // reverse the vector back into ascending order std::reverse(best.begin(), best.end()); return best; }// end of DynamicKnapsack bool IsSolution(vector<PackageSet>& pset, int index, int currWeight) { return std::find(pset.at(index).appearances.begin(), pset.at(index).appearances.end(), currWeight) != pset.at(index).appearances.end(); }// end of IsSolution vector<PackageStats> ReturnBest(vector<PackageStats>& packages, vector<int>& knapResult) { vector<PackageStats> best; for(unsigned x=0; x < knapResult.size(); ++x) { best.push_back(packages.at(knapResult.at(x))); } return best; }// end of ReturnBest ~Project5(){} }; #endif // http://programmingnotes.org/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139 // =============================================================================//    Author: K Perkins//    Date:   Nov 3, 2013//    Taken From: http://programmingnotes.org///    File:  Project5.h//    Description: This is a simple class which holds the functions for //       project 5// =============================================================================#ifndef PROJECT5_H#define PROJECT5_H #include <vector>#include <algorithm>#include "Project2.h"using std::vector; struct PackageSet{ int index; int weight; vector<int> appearances;}; class Project5{public: Project5(){}  vector<int> DynamicKnapsack(int packageWeight[], int packageVotes[], int numPackages, int maxWeight) { // declare variables vector<int> best; vector<int> temp; vector<PackageSet> pset; int** T = new int*[numPackages+1]; int deleted = 0; int currWeight = maxWeight; bool dontCheck = false;   for(int x=0; x <= numPackages; ++x) { T[x] = new int[maxWeight+1]; PackageSet access; dontCheck = false; temp.clear(); for(int y=0; y <= maxWeight; ++y) { if(x==0 || y==0) { T[x][y] = 0; } else if(packageWeight[x-1] <= y) { T[x][y] = std::max(T[x-1][y-packageWeight[x-1]] + packageVotes[x-1], T[x-1][y]); if(T[x][y] == (T[x-1][y-packageWeight[x-1]] + packageVotes[x-1])) { // if we find a valid packet, place it into // the temp vector for storage if(!dontCheck && !(std::find(temp.begin(), temp.end(), packageWeight[x-1]) != temp.end())) { temp.push_back(packageWeight[x-1]); } // find all of the weight instances where // this packet is "valid" access.appearances.push_back(y); dontCheck = true; } } else { T[x][y] = T[x-1][y]; } }// end for loop  // gather info about the packet we just found if((std::find(temp.begin(), temp.end(), packageWeight[x-1]) != temp.end())) { access.index = x-1; access.weight = packageWeight[x-1]; pset.push_back(access); } // memory management, used to delete // array indexes thats no longer in use if(x > 1) { delete[] T[deleted++]; } }// end for loop   delete[] T; // obtain the best possible knapsack solutuion, and save // their array indexes into a vector, starting from the end // NOTE: this places the knapsack solution in opposite (reverse) order for(int x = pset.size()-1; x >= 0; --x) { if(IsSolution(pset, x, currWeight)) { best.push_back(pset.at(x).index); currWeight -= pset.at(x).weight; } pset.pop_back(); } // reverse the vector back into ascending order std::reverse(best.begin(), best.end());  return best; }// end of DynamicKnapsack  bool IsSolution(vector<PackageSet>& pset, int index, int currWeight) { return std::find(pset.at(index).appearances.begin(), pset.at(index).appearances.end(), currWeight) != pset.at(index).appearances.end(); }// end of IsSolution  vector<PackageStats> ReturnBest(vector<PackageStats>& packages, vector<int>& knapResult) { vector<PackageStats> best; for(unsigned x=0; x < knapResult.size(); ++x) { best.push_back(packages.at(knapResult.at(x))); } return best; }// end of ReturnBest  ~Project5(){}};#endif // http://programmingnotes.org/ ```

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Note: Dont forget to include the input file!

The following is sample output:

`=== RUN #1 ===`

``` n = 36149, W = 65536 -- Dynamic Search Solution -- - Number of packages generated in this set: 764 - First 20 packages.. debianutils 90 128329 libgcc1 46 128327 debconf 168 121503 grep 595 121426 gzip 142 121346 sed 261 121220 findutils 805 121173 lsb-base 26 121121 sysv-rc 80 121092 sysvinit-utils 116 121078 base-files 65 121072 initscripts 93 121037 util-linux 846 121022 mount 272 120961 libselinux1 109 120918 cron 120 120872 base-passwd 49 120856 tzdata 488 120813 logrotate 64 120745 popularity-contest 67 120729 Total Size = 65536 -- Total Votes = 25250749 It took 33500 clicks (33.50 seconds) === RUN #2 === n = 36149, W = 800000 -- Dynamic Search Solution -- - Number of packages generated in this set: 4406 - First 20 packages.. debianutils 90 128329 libgcc1 46 128327 dpkg 2672 128294 perl-base 1969 127369 debconf 168 121503 grep 595 121426 gzip 142 121346 login 980 121332 coreutils 6505 121240 bash 1673 121229 sed 261 121220 findutils 805 121173 lsb-base 26 121121 sysv-rc 80 121092 sysvinit-utils 116 121078 base-files 65 121072 initscripts 93 121037 util-linux 846 121022 mount 272 120961 libselinux1 109 120918 Total Size = 800000 -- Total Votes = 41588693 ```

```It took 608760 clicks (608.76 seconds) ```