Consider the Integer Knapsack Problem. Unlike 0/1 Knapsack problem which restric

Question

Consider the Integer Knapsack Problem. Unlike 0/1 Knapsack problem which restricts xi
to be either 0 or 1, Integer Knapsack Problem allows xi to be any integer >= 0 (that is, we
assume that unlimited copies of ith object are available, for all i).
(a) Obtain the dynamic programming functional equation to solve the Integer Knapsack
Problem.
(b) Give an algorithm to implement your functional equation.
(c) What is the complexity of your algorithm?

Explanation / Answer

#include int max(int a,int b) { return a>b?a:b; } int Knapsack(int items,int weight[],int value[],int maxWeight) { int dp[items+1][maxWeight+1]; /* dp[i][w] represents maximum value that can be attained if the maximum weight is w and items are chosen from 1...i */ /* dp[0][w] = 0 for all w because we have chosen 0 items */ int iter,w; for(iter=0;iter

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---