Answered: Using the incomplete programming code…

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Related questions

Question

Question 1

Using the incomplete programming code given, complete the code using dynamic programming, to reproduce the results in the following Table 1.
(C++)

#include<iostream>
using namespace std;

const int W = //***WRITE YOUR CODE HERE***//; // max knapsack capacity

//==========================================================================
// Dynamic Programming function for solving Knapsack Problem
void Knapsack(int i, int j, int w[], int n, int v[], int F[][W]){
//==========================================================================
// i: iteration index for item numbers (i: 0~n)
// j: iteration index for weights/capacity (j: 0~max knapsack capacity W)
// w: current item's weight
// v: current item's value
// Output: Values of F(i,j)
//---------------------------------------------------------------------------


//Instruction: Write your code to calculate F(i,j). Include comments

// ***WRITE YOUR CODE HERE***
// ***WRITE YOUR CODE HERE***
// ***WRITE YOUR CODE HERE***

}

//===============
// Main Function
int main(void){
//===============

// number of items
const int n /* =? ***WRITE YOUR CODE HERE*** */

int i; // item: 1 <= i <= n
int j; // capacity: 1 <= j <= W


int weight[] = {/* ***WRITE YOUR CODE HERE*** */}; // weight of each item
int value[] = {/* ***WRITE YOUR CODE HERE*** */}; // value of each item


// Instruction: Initialize F
//F: dynamic programming table/matrix, containing values of F(i,j)
int F.. // *** WRITE YOUR CODE HERE *** (for F)


// call the dynamic programming function
Knapsack(i, j, weight, n, value, F);


// Instruction: Display your output, containing values of F(i,j)

//NOTES:
/* Output can be in the form of a TABLE, or:
F(0,0) = 0
F(0,1) = 0
F(0,2) = 0
.. (continues until the end)
*/


// *** WRITE YOUR CODE HERE ***
// *** WRITE YOUR CODE HERE ***
// *** WRITE YOUR CODE HERE ***




return 0;
}

Dynamic Programming Table
capacity j
i
0
1
2
3
4 5
0
0
0 0 0
0
0
1
0
0 12 12 12 12
2
0
10 12
22 22 22
3
0 10 12 22
30
32
4 0
10
15
25 30
37
F(4,5) = 37
65
W₁ = 2, V₁ = 12
W₂ = 1, V₂ = 10
W3 = 3, V3 = 20
W4 = 2, V4 = 15
max
ⒸS. Turaev CSC 3102 DSA II
F(i-1, j),
v¡ + F(i − 1, j − w;)

Expert Solution

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Follow-up Questions

Read through expert solutions to related follow-up questions below.

Follow-up Question

I'm still unsure how to incorporate the answer into the incomplete code. I've attached some images to help understand the situation. It would be really helpful if you could fill in the code according to as shown in the images.