Is this problem a knapsack problem?

Dynamic Programming (DP): What is the complexity of the best known algorithm for the 0-1 exact knapsack problem?

• I am trying to understand if the *exact 0-1 knapsack problem* is also pseudo-polynomial time. Some clarifications: We are given n stones of varying and known weights, and some number W. We need to find any subset of the stones (if it exists) that sum *exactly* to W. Note: 0-1 implies that each weight can occur exactly zero or one times in the "bag" Is this pseudo-polynomial in W?

• Answer:

  This is just the subset sum problem, and there is an obvious O(N*W) algorithm. Let the weights of stones be stored in ar[N]. We use dynamic programming to check whether a sum of W can be obtained: bool poss[W+1]; // Initialised to false poss[0]=true; for(int i=0;i<N;i++) { for(int j=W;j>=ar[i];j--) if(poss[j-ar[i]])poss[j]=true; if(poss[W])return true; } return false; For a non-pseudopolynomial but usually much faster algorithm when W>2^(N/2), see .