The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
62 views

In the knapsack problem we are given a set of n items, where each item i is specified by a size si and a value vi. We are also given a size bound S (the size of our knapsack). The goal is to find the subset of items of maximum total value such that sum of their sizes is at most S (they all fit into the knapsack).

We are trying to use Dynamic programming paradigm to reduce the time complexity for the solution. The algorithm follows

Value(n,S)
{
if (n == 0) return 0;
if (arr[n][S] != unknown) return arr[n][S];
if (s_n > S) result = Value(n-1,S);
else result = max{v_n + Value(n-1, S-s_n), Value(n-1, S)};
XXXX
return result;
}

What statement can go in the place of XXXX to make algorithm complete?

(A) No Statement is needed. It is already complete algorithm.

(B) arr[S][n]= result;

(C) arr[n][n]= result;

(D) arr[n][S] = result;

asked in Algorithms by Active (4.2k points) | 62 views
0
D ...
0
can you explain please?

Please log in or register to answer this question.

Related questions

0 votes
0 answers
1
+1 vote
1 answer
6
+5 votes
2 answers
7
asked Jan 21, 2017 in Algorithms by Sarvottam Patel Active (1.1k points) | 436 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,514 questions
48,528 answers
155,009 comments
63,366 users