Using the incomplete programming code given, complete the code using dynamic programming, to reproduce the results in the following Table 1. (C++) #include using namespace std; const int W = //***WRITE YOUR CODE HERE***//; // max knapsack capacity //==========================================================================
Question 1
Using the incomplete
(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;
}
Step by step
Solved in 2 steps
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.
![ALMACENANGA
1
//========
// Dynamic Programming - Knapsack
//=======
#include<iostream>
using namespace std;
8
9
const int W = //***WRITE YOUR CODE HERE***//; // max knapsack capacity
11 //===
12
// Dynamic Programming function for solving Knapsack Problem
13 void Knapsack (int i, int j, int w[], int n, int v[], int F[][W]){
14 //===============
======
========
// i: iteration index for item numbers (i: 0~n)
16
// j: iteration index for weights/capacity (j: 0~max knapsack capacity W)
// w: current item's weight
17
// v: current item's value
// Output: Values of F(i, j)
//-
22
23
//Instruction: Write your code to calculate F(i,j). Include comments
24
// ***WRITE YOUR CODE HERE***
// ***WRITE YOUR CODE HERE***
// ***WRITE YOUR CODE HERE***
2
3
4
5
6
7
10
15
18
19
20
21
25
26
27
28
29
}](https://content.bartleby.com/qna-images/question/65b5aa14-280a-4db3-87ee-5f6b39edfbe3/0cd55eae-d67d-4265-83eb-de03160a88b5/irwwhfd_processed.png)
![30 31 32
//=======
// Main Function
33 int main(void) {
34 //=======
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
364556句品的龙12及4575
68
69
70
}
// 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*** */};
int value[] = {/* ***WRITE YOUR CODE HERE*** */};
// 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)
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;
// weight of each item
// value of each item](https://content.bartleby.com/qna-images/question/65b5aa14-280a-4db3-87ee-5f6b39edfbe3/0cd55eae-d67d-4265-83eb-de03160a88b5/8x5g28_processed.png)
by Bartleby Expert
