Answers.Body: <p>I think there are at least three points that you need to think before implement Hill-Climbing (HC) algorithm:</p>
  
  <p>First, the initial state. In HC, people usually use a "temporary solution" for the initial state. You can use an empty knapscak, but I prefer to randomly pick items and put it in the knapsack as the initial state. You can use a binary array to save the "pickup status" of each item such that if <span class="math-container">$a_i=1$</span> then you pick the <span class="math-container">$i$</span>-th item and if <span class="math-container">$a_i=0$</span> then you don't pick the <span class="math-container">$i$</span>-th item.</p>
  
  <p>The next is the heuristic function. A function that evaluate your current state. Actually, you can define it freely (like the initial state) as long as the function can evaluate which state is better than the others. You can use a simple one:</p>
  
  <p><span class="math-container">$$
  h =
      \begin{cases}
        -1, &amp; \text{if}\ \sum (w_i \times a_i) &gt; \text{MaxWeight} \\
        \sum (v_i \times a_i), &amp; \text{otherwise}
      \end{cases}
  $$</span></p>
  
  <p>with <span class="math-container">$w_i$</span> and <span class="math-container">$v_i$</span> is the weight and the value of the <span class="math-container">$i$</span>-th item respectively. One of the disadvantage of this function is if you have more than one invalid state (a state with the total weight is more than the limit), they have the same value, which is <span class="math-container">$-1$</span>.</p>
  
  <p>The last is the method to generate the neighbors of the current state. Once again, you are also free to define the method that you will use. I think your proposed actions are good enough:</p>
  
  <ul>
  <li>reverse the status of an item (1 to 0 or 0 to 1). That means I add or reduce the item on the current state.</li>
  <li>swap the status two items that have different value. Formally swap <span class="math-container">$a_i$</span> and <span class="math-container">$a_j$</span> with <span class="math-container">$ i \neq j$</span> and <span class="math-container">$ a_i \neq a_j$</span>. That means I swap the item that I picked before with the item that I didn't pick before</li>
  </ul>
  
  <p>Then, after you define everything you can run the algorithm as explained in <a href="https://en.wikipedia.org/wiki/Hill_climbing#Pseudocode" rel="nofollow noreferrer">Wikipedia</a>:</p>
  
  <pre><code>currentNode = startNode;
  loop do
      L = NEIGHBORS(currentNode);
      nextEval = -INF;
      nextNode = NULL;
      for all x in L 
          if (EVAL(x) &gt; nextEval)
              nextNode = x;
              nextEval = EVAL(x);
      if nextEval &lt;= EVAL(currentNode)
          //Return current node since no better neighbors exist
          return currentNode;
      currentNode = nextNode;
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-05T03:48:08.447Z
Answers.LastActivityDate: 2019-03-05T03:48:08.447Z
Answers.UserDisplayName: malioboro
Body: <p>I need to solve the knapsack problem using hill climbing algorithm (I need to write a program). But I'm clueless about how to do it.</p>
  
  <p>My code should contain a method called <code>knapsack</code>, the method takes two parameters, the first is a 2xN array of integers that represents the items and their weight and value, and the second is an integer that represents the maximum weight of the knapsack. I can assume that the initial state is an empty knapsack, and the actions are either putting objects in the Knapsack or swapping objects from in and out of the knapsack.</p>
  
Tags: <search><hill-climbing><knapsack-problem>
Title: How do I solve the knapsack problem using the hill climbing algorithm?
UserDisplayName: lujain
ThreadText: # How do I solve the knapsack problem using the hill climbing algorithm?
  
  (Asked by: username_0 on 2017-03-22)
  
  I need to solve the knapsack problem using hill climbing algorithm (I need to write a program). But I'm clueless about how to do it.
  
  My code should contain a method called `knapsack`, the method takes two parameters, the first is a 2xN array of integers that represents the items and their weight and value, and the second is an integer that represents the maximum weight of the knapsack. I can assume that the initial state is an empty knapsack, and the actions are either putting objects in the Knapsack or swapping objects from in and out of the knapsack.
  
  **Tags:** search, hill-climbing, knapsack-problem
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-05. Score: 2
  
  I think there are at least three points that you need to think before implement Hill-Climbing (HC) algorithm:
  
  First, the initial state. In HC, people usually use a "temporary solution" for the initial state. You can use an empty knapscak, but I prefer to randomly pick items and put it in the knapsack as the initial state. You can use a binary array to save the "pickup status" of each item such that if $a\_i=1$ then you pick the $i$-th item and if $a\_i=0$ then you don't pick the $i$-th item.
  
  The next is the heuristic function. A function that evaluate your current state. Actually, you can define it freely (like the initial state) as long as the function can evaluate which state is better than the others. You can use a simple one:
  
  $$
  h =
  \begin{cases}
  -1, & \text{if}\ \sum (w\_i \times a\_i) > \text{MaxWeight} \\
  \sum (v\_i \times a\_i), & \text{otherwise}
  \end{cases}
  $$
  
  with $w\_i$ and $v\_i$ is the weight and the value of the $i$-th item respectively. One of the disadvantage of this function is if you have more than one invalid state (a state with the total weight is more than the limit), they have the same value, which is $-1$.
  
  The last is the method to generate the neighbors of the current state. Once again, you are also free to define the method that you will use. I think your proposed actions are good enough:
  
  * reverse the status of an item (1 to 0 or 0 to 1). That means I add or reduce the item on the current state.
  * swap the status two items that have different value. Formally swap $a\_i$ and $a\_j$ with $ i \neq j$ and $ a\_i \neq a\_j$. That means I swap the item that I picked before with the item that I didn't pick before
  
  Then, after you define everything you can run the algorithm as explained in [Wikipedia](https://en.wikipedia.org/wiki/Hill_climbing#Pseudocode):
  
  ```
  currentNode = startNode;
  loop do
      L = NEIGHBORS(currentNode);
      nextEval = -INF;
      nextNode = NULL;
      for all x in L 
          if (EVAL(x) > nextEval)
              nextNode = x;
              nextEval = EVAL(x);
      if nextEval <= EVAL(currentNode)
          //Return current node since no better neighbors exist
          return currentNode;
      currentNode = nextNode;
  
  ```
  
  
  ---
  
  