Snippets

Camilo Rocha KS naive

Created by Former user
View revision

File ks_naive.py Added

  • Ignore whitespace
  • Hide word diff 
+# input: v[0..N) and w[0..N) arrays of natural numbers, N>=0, and C>=0
+#
+# output: Maximum retribution by choosing elements with individual
+#         retribution and weight in v[0..N) and w[0..N), respectively,
+#         to carry in a knapsack with weight capacity C
+#
+# exponential (in N ans C) naive solution
+
+def ks_naive(v,w,C):
+  return ks_aux(v,w,len(v),C)
+
+def ks_aux(v,w,n,c):
+  ans = None
+  if n==0: ans = 0
+  else:
+    ans = ks_aux(v,w,n-1,c)
+    if w[n-1]<=c:
+      ans = max(ans,v[n-1]+ks_aux(v,w,n-1,c-w[n-1]))
+  return ans
HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.