+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: Homework (https://python-forum.io/forum-9.html)
+--- Thread: Please Help! (/thread-30033.html)
Please Help! - bntayfur - Oct-01-2020
I tried so many times but i couldn't do it :(
The steps are all below, someone please help me!
Algorithm 1 Greedy Algorithm for the Continuous Knapsack Problem
1: Input: n items with size si, value vi
2: Input: Knapsack capacity K
3: Set solution vector x equal to 0 for all xi
4: Set current objective function value z = 0
5: Calculate ri =vi/si for all items i = 1, . . . , n
6: Sort the ri values in non-increasing order, place in vector R
7: Set u, representing the used knapsack capacity, to zero
8: Set iterator i to 1
9: while u < K do
10: if si + u ≤ K then
11: Set xi = 1
12: Set u = u + si
13: Set z = z + vi
14: else if si + u > K then
15: Set xi
to the maximum amount of item i that can be placed in the knapsack
16: Set u = u + sixi
(Note, this should equal K)
17: Set z = z + vixi
18: end if
19: Set i = i + 1
20: end while
21: Return the solution vector x and objective function value z
RE: Please Help! - scidam - Oct-01-2020
This is almost a valid Python program. What did you try so far?
It seems that you need a bit of effort to turn this algorithm into working program.
RE: Please Help! - bntayfur - Oct-01-2020
def knapSack(K,s,v,n):
z=0
u=0
listx=[]
R=[]
for k in s:
m=v[k]
r= m/k
R.append(r)
R.sort()
if s.index(k)== len(s)-1:
R.reverse()
if k + u <= K:
x = 1
u = u + k
z = z + m
elif k + u > K:
x=0
u = K
z = z + m*x
listx.append(x)
print(x)
print(z)
# To test above function
v = [60, 100, 120]
s = [10, 20, 30]
K = 50
n = len(v)
knapSack(K,s,v,n)def knapSack(K,s,v,n):
z=0
u=0
i=1
listx=[]
R=[]
for k in s:
m=v[k]
r= m/k
R.append(r)
R.sort()
if s.index(k)== len(s)-1:
R.reverse()
while i <= n:
if k + u <= K:
x = 1
u = u + k
z = z + m
elif k + u > K:
x=0
u = K
z = z + m*x
listx.append(x)
i = i + 1
print(x)
print(z)
# To test above function
v = [60, 100, 120]
s = [10, 20, 30]
K = 50
n = len(v)
knapSack(K,s,v,n) 2 things i tried so far, gone wrong, i don't know python so couldn't really figure out :(
something wrong with code - bntayfur - Oct-01-2020
1: Input: n items with size si,value vi
2: Input: Knapsack capacity K
3: Set solution vector x equal to 0 for all xi
4: Set current objective function value z = 0
5: Calculate ri =vi/si for all items i = 1, . . . , n
6: Sort the ri values in non-increasing order, place in vector R
7: Set u, representing the used knapsack capacity, to zero
8: Set iterator i to 1
9: while u < K do
10: if si + u ≤ K then
11: Set xi = 1
12: Set u = u + si
13: Set z = z + vi
14: else if si + u > K then
15: Set xi
to the maximum amount of item i that can be placed in the knapsack
16: Set u = u + sixi
(Note, this should equal K)
17: Set z = z + vixi
18: end if
19: Set i = i + 1
20: end while
21: Return the solution vector x and objective function value z
def knapSack(K,s,v,n):
z=0
u=0
i=1
listx=[]
R=[]
for k in s:
m=v[k]
r= m/k
R.append(r)
R.sort()
if s.index(k)== len(s)-1:
R.reverse()
while i <= n:
if k + u <= K:
x = 1
u = u + k
z = z + m
elif k + u > K:
x=0
u = K
z = z + m*x
listx.append(x)
i = i + 1
print(x)
print(z)
# To test above function
v = [60, 100, 120]
s = [10, 20, 30]
K = 50
n = len(v)
knapSack(K,s,v,n)What's wrong someone help me please not good with python :(
RE: Please Help! - ibreeden - Oct-02-2020
Is this the error you get?
Error:Traceback (most recent call last):
File "/home/ibreeden/PycharmProjects/kanweg/hello.py", line 37, in <module>
knapSack(K, s, v, n)
File "/home/ibreeden/PycharmProjects/kanweg/hello.py", line 8, in knapSack
m = v[k]
IndexError: list index out of rangeThe message is quite clear. In line 8 you try to assign v[k] and the index (k) is out of range.
"v" is a list of 3 elements:
v = [60, 100, 120]So you can only access: v[0], v[1] and v[2]
"k" gets te values of "for k in s". "s" has the values:
s = [10, 20, 30]So in the first loop "k" gets the value 10. Then v[10] will be accessed which is impossible because only access v[0], v[1] and v[2].
That is the error you get.