JavaScript/Dynamic-Programming/ZeroOneKnapsack.js at master · Guduly/JavaScript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 */

constzeroOneKnapsack=(arr,n,cap,cache)=>{
if(cap===0||n===0){
cache[n][cap]=0
returncache[n][cap]
}
if(cache[n][cap]!==-1){
returncache[n][cap]
}
if(arr[n-1][0]<=cap){
cache[n][cap]=Math.max(arr[n-1][1]+zeroOneKnapsack(arr,n-1,cap-arr[n-1][0],cache),zeroOneKnapsack(arr,n-1,cap,cache))
returncache[n][cap]
}else{
cache[n][cap]=zeroOneKnapsack(arr,n-1,cap,cache)
returncache[n][cap]
}
}

constexample=()=>{
/*
 Problem Statement:
 You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
 You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.

 Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
 */
letinput=`1
 4 5
 1 8
 2 4
 3 0
 2 5
 2 3`

input=input.trim().split('\n')
input.shift()
constlength=input.length

constoutput=[]

leti=0
while(i<length){
constcap=Number(input[i].trim().split(' ')[0])
constcurrlen=Number(input[i].trim().split(' ')[1])
letj=i+1
constarr=[]
while(j<=i+currlen){
arr.push(input[j])
j++
}
constnewArr=arr.map(e=>
e.trim().split(' ').map(Number)
)
constcache=[]
for(leti=0;i<=currlen;i++){
consttemp=[]
for(letj=0;j<=cap;j++){
temp.push(-1)
}
cache.push(temp)
}
constresult=zeroOneKnapsack(newArr,currlen,cap,cache)
output.push(result)
i+=currlen+1
}

returnoutput
}

export{zeroOneKnapsack,example}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 */

constzeroOneKnapsack=(arr,n,cap,cache)=>{
if(cap===0||n===0){
cache[n][cap]=0
returncache[n][cap]
}
if(cache[n][cap]!==-1){
returncache[n][cap]
}
if(arr[n-1][0]<=cap){
cache[n][cap]=Math.max(arr[n-1][1]+zeroOneKnapsack(arr,n-1,cap-arr[n-1][0],cache),zeroOneKnapsack(arr,n-1,cap,cache))
returncache[n][cap]
}else{
cache[n][cap]=zeroOneKnapsack(arr,n-1,cap,cache)
returncache[n][cap]
}
}

constexample=()=>{
/*
 Problem Statement:
 You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
 You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.

 Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
 */
letinput=`1
 4 5
 1 8
 2 4
 3 0
 2 5
 2 3`

input=input.trim().split('\n')
input.shift()
constlength=input.length

constoutput=[]

leti=0
while(i<length){
constcap=Number(input[i].trim().split(' ')[0])
constcurrlen=Number(input[i].trim().split(' ')[1])
letj=i+1
constarr=[]
while(j<=i+currlen){
arr.push(input[j])
j++
}
constnewArr=arr.map(e=>
e.trim().split(' ').map(Number)
)
constcache=[]
for(leti=0;i<=currlen;i++){
consttemp=[]
for(letj=0;j<=cap;j++){
temp.push(-1)
}
cache.push(temp)
}
constresult=zeroOneKnapsack(newArr,currlen,cap,cache)
output.push(result)
i+=currlen+1
}

returnoutput
}

export{zeroOneKnapsack,example}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 */

constzeroOneKnapsack=(arr,n,cap,cache)=>{
if(cap===0||n===0){
cache[n][cap]=0
returncache[n][cap]
}
if(cache[n][cap]!==-1){
returncache[n][cap]
}
if(arr[n-1][0]<=cap){
cache[n][cap]=Math.max(arr[n-1][1]+zeroOneKnapsack(arr,n-1,cap-arr[n-1][0],cache),zeroOneKnapsack(arr,n-1,cap,cache))
returncache[n][cap]
}else{
cache[n][cap]=zeroOneKnapsack(arr,n-1,cap,cache)
returncache[n][cap]
}
}

constexample=()=>{
/*
 Problem Statement:
 You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
 You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.

 Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
 */
letinput=`1
 4 5
 1 8
 2 4
 3 0
 2 5
 2 3`

input=input.trim().split('\n')
input.shift()
constlength=input.length

constoutput=[]

leti=0
while(i<length){
constcap=Number(input[i].trim().split(' ')[0])
constcurrlen=Number(input[i].trim().split(' ')[1])
letj=i+1
constarr=[]
while(j<=i+currlen){
arr.push(input[j])
j++
}
constnewArr=arr.map(e=>
e.trim().split(' ').map(Number)
)
constcache=[]
for(leti=0;i<=currlen;i++){
consttemp=[]
for(letj=0;j<=cap;j++){
temp.push(-1)
}
cache.push(temp)
}
constresult=zeroOneKnapsack(newArr,currlen,cap,cache)
output.push(result)
i+=currlen+1
}

returnoutput
}

export{zeroOneKnapsack,example}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 */

constzeroOneKnapsack=(arr,n,cap,cache)=>{
if(cap===0||n===0){
cache[n][cap]=0
returncache[n][cap]
}
if(cache[n][cap]!==-1){
returncache[n][cap]
}
if(arr[n-1][0]<=cap){
cache[n][cap]=Math.max(arr[n-1][1]+zeroOneKnapsack(arr,n-1,cap-arr[n-1][0],cache),zeroOneKnapsack(arr,n-1,cap,cache))
returncache[n][cap]
}else{
cache[n][cap]=zeroOneKnapsack(arr,n-1,cap,cache)
returncache[n][cap]
}
}

constexample=()=>{
/*
 Problem Statement:
 You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
 You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.

 Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
 */
letinput=`1
 4 5
 1 8
 2 4
 3 0
 2 5
 2 3`

input=input.trim().split('\n')
input.shift()
constlength=input.length

constoutput=[]

leti=0
while(i<length){
constcap=Number(input[i].trim().split(' ')[0])
constcurrlen=Number(input[i].trim().split(' ')[1])
letj=i+1
constarr=[]
while(j<=i+currlen){
arr.push(input[j])
j++
}
constnewArr=arr.map(e=>
e.trim().split(' ').map(Number)
)
constcache=[]
for(leti=0;i<=currlen;i++){
consttemp=[]
for(letj=0;j<=cap;j++){
temp.push(-1)
}
cache.push(temp)
}
constresult=zeroOneKnapsack(newArr,currlen,cap,cache)
output.push(result)
i+=currlen+1
}

returnoutput
}

export{zeroOneKnapsack,example}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 */

constzeroOneKnapsack=(arr,n,cap,cache)=>{
if(cap===0||n===0){
cache[n][cap]=0
returncache[n][cap]
}
if(cache[n][cap]!==-1){
returncache[n][cap]
}
if(arr[n-1][0]<=cap){
cache[n][cap]=Math.max(arr[n-1][1]+zeroOneKnapsack(arr,n-1,cap-arr[n-1][0],cache),zeroOneKnapsack(arr,n-1,cap,cache))
returncache[n][cap]
}else{
cache[n][cap]=zeroOneKnapsack(arr,n-1,cap,cache)
returncache[n][cap]
}
}

constexample=()=>{
/*
 Problem Statement:
 You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
 You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.

 Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
 */
letinput=`1
 4 5
 1 8
 2 4
 3 0
 2 5
 2 3`

input=input.trim().split('\n')
input.shift()
constlength=input.length

constoutput=[]

leti=0
while(i<length){
constcap=Number(input[i].trim().split(' ')[0])
constcurrlen=Number(input[i].trim().split(' ')[1])
letj=i+1
constarr=[]
while(j<=i+currlen){
arr.push(input[j])
j++
}
constnewArr=arr.map(e=>
e.trim().split(' ').map(Number)
)
constcache=[]
for(leti=0;i<=currlen;i++){
consttemp=[]
for(letj=0;j<=cap;j++){
temp.push(-1)
}
cache.push(temp)
}
constresult=zeroOneKnapsack(newArr,currlen,cap,cache)
output.push(result)
i+=currlen+1
}

returnoutput
}

export{zeroOneKnapsack,example}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 */

constzeroOneKnapsack=(arr,n,cap,cache)=>{
if(cap===0||n===0){
cache[n][cap]=0
returncache[n][cap]
}
if(cache[n][cap]!==-1){
returncache[n][cap]
}
if(arr[n-1][0]<=cap){
cache[n][cap]=Math.max(arr[n-1][1]+zeroOneKnapsack(arr,n-1,cap-arr[n-1][0],cache),zeroOneKnapsack(arr,n-1,cap,cache))
returncache[n][cap]
}else{
cache[n][cap]=zeroOneKnapsack(arr,n-1,cap,cache)
returncache[n][cap]
}
}

constexample=()=>{
/*
 Problem Statement:
 You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
 You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.

 Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
 */
letinput=`1
 4 5
 1 8
 2 4
 3 0
 2 5
 2 3`

input=input.trim().split('\n')
input.shift()
constlength=input.length

constoutput=[]

leti=0
while(i<length){
constcap=Number(input[i].trim().split(' ')[0])
constcurrlen=Number(input[i].trim().split(' ')[1])
letj=i+1
constarr=[]
while(j<=i+currlen){
arr.push(input[j])
j++
}
constnewArr=arr.map(e=>
e.trim().split(' ').map(Number)
)
constcache=[]
for(leti=0;i<=currlen;i++){
consttemp=[]
for(letj=0;j<=cap;j++){
temp.push(-1)
}
cache.push(temp)
}
constresult=zeroOneKnapsack(newArr,currlen,cap,cache)
output.push(result)
i+=currlen+1
}

returnoutput
}

export{zeroOneKnapsack,example}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 */

constzeroOneKnapsack=(arr,n,cap,cache)=>{
if(cap===0||n===0){
cache[n][cap]=0
returncache[n][cap]
}
if(cache[n][cap]!==-1){
returncache[n][cap]
}
if(arr[n-1][0]<=cap){
cache[n][cap]=Math.max(arr[n-1][1]+zeroOneKnapsack(arr,n-1,cap-arr[n-1][0],cache),zeroOneKnapsack(arr,n-1,cap,cache))
returncache[n][cap]
}else{
cache[n][cap]=zeroOneKnapsack(arr,n-1,cap,cache)
returncache[n][cap]
}
}

constexample=()=>{
/*
 Problem Statement:
 You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
 You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.

 Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
 */
letinput=`1
 4 5
 1 8
 2 4
 3 0
 2 5
 2 3`

input=input.trim().split('\n')
input.shift()
constlength=input.length

constoutput=[]

leti=0
while(i<length){
constcap=Number(input[i].trim().split(' ')[0])
constcurrlen=Number(input[i].trim().split(' ')[1])
letj=i+1
constarr=[]
while(j<=i+currlen){
arr.push(input[j])
j++
}
constnewArr=arr.map(e=>
e.trim().split(' ').map(Number)
)
constcache=[]
for(leti=0;i<=currlen;i++){
consttemp=[]
for(letj=0;j<=cap;j++){
temp.push(-1)
}
cache.push(temp)
}
constresult=zeroOneKnapsack(newArr,currlen,cap,cache)
output.push(result)
i+=currlen+1
}

returnoutput
}

export{zeroOneKnapsack,example}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * A Dynamic Programming based solution for calculating Zero One Knapsack
 * https://en.wikipedia.org/wiki/Knapsack_problem
 */

constzeroOneKnapsack=(arr,n,cap,cache)=>{
if(cap===0||n===0){
cache[n][cap]=0
returncache[n][cap]
}
if(cache[n][cap]!==-1){
returncache[n][cap]
}
if(arr[n-1][0]<=cap){
cache[n][cap]=Math.max(arr[n-1][1]+zeroOneKnapsack(arr,n-1,cap-arr[n-1][0],cache),zeroOneKnapsack(arr,n-1,cap,cache))
returncache[n][cap]
}else{
cache[n][cap]=zeroOneKnapsack(arr,n-1,cap,cache)
returncache[n][cap]
}
}

constexample=()=>{
/*
 Problem Statement:
 You are a thief carrying a single bag with limited capacity S. The museum you stole had N artifact that you could steal. Unfortunately you might not be able to steal all the artifact because of your limited bag capacity.
 You have to cherry pick the artifact in order to maximize the total value of the artifacts you stole.

 Link for the Problem: https://www.hackerrank.com/contests/srin-aadc03/challenges/classic-01-knapsack
 */
letinput=`1
 4 5
 1 8
 2 4
 3 0
 2 5
 2 3`

input=input.trim().split('\n')
input.shift()
constlength=input.length

constoutput=[]

leti=0
while(i<length){
constcap=Number(input[i].trim().split(' ')[0])
constcurrlen=Number(input[i].trim().split(' ')[1])
letj=i+1
constarr=[]
while(j<=i+currlen){
arr.push(input[j])
j++
}
constnewArr=arr.map(e=>
e.trim().split(' ').map(Number)
)
constcache=[]
for(leti=0;i<=currlen;i++){
consttemp=[]
for(letj=0;j<=cap;j++){
temp.push(-1)
}
cache.push(temp)
}
constresult=zeroOneKnapsack(newArr,currlen,cap,cache)
output.push(result)
i+=currlen+1
}

returnoutput
}

export{zeroOneKnapsack,example}