<jupyter_start><jupyter_text>**0/1 Knapsack Problem using (inefficient) Greedy Algorithm**---<NAME> - 1301170066<jupyter_code># Deklarasi class
class SimpleClass(object):
    pass
  
def ratio(t):
    return t.v/t.w
# Inisialisasi banyak knapsack dan maksimal weight
n = input("Masukkan banyak knapsack: ")
W_max = input("Masukkan berat maksimal: ")
# Inisialisasi knapsack
knapsack = []
knapsack_weight = []
knapsack_value = []
knapsack_density = []

for count in range(1,int(n)+1):
    print("Knapsack ke-", count)
    x = SimpleClass()
    x.i = count
    x.v = int(input("Value: "))
    x.w = int(input("Weight: "))
    knapsack.append(x)
    print()
# Sort knapsack by weight, value, and density yeah!

knapsack_weight = knapsack.copy()
knapsack_value = knapsack.copy()
knapsack_density = knapsack.copy()

# print("Sorted by Weight")
# for x in range(len(knapsack_weight)): 
#     print("Knapsack", knapsack_weight[x].i,":")
#     print("Value:", knapsack_weight[x].v)
#     print("Weight:", knapsack_weight[x].w)
#     print()

# print("=====================================")
# print("Sorted by Value")
# for x in range(len(knapsack_value)): 
#     print("Knapsack", knapsack_value[x].i,":")
#     print("Value:", knapsack_value[x].v)
#     print("Weight:", knapsack_value[x].w)
#     print()

# print("=====================================")
# print("Sorted by Density")
# for x in range(len(knapsack_density)): 
#     print("Knapsack", knapsack_density[x].i,":")
#     print("Value:", knapsack_density[x].v)
#     print("Weight:", knapsack_density[x].w)
#     print("Ratio:", ratio(knapsack_density[x]))
#     print()

knapsack_weight.sort(key=lambda x : x.w,reverse=True)
knapsack_value.sort(key=lambda x : x.v,reverse=True)
knapsack_density.sort(key=ratio,reverse=True)

# print("=====================================")
# print("Sorted by Weight")
# for x in range(len(knapsack_weight)): 
#     print("Knapsack", knapsack_weight[x].i,":")
#     print("Value:", knapsack_weight[x].v)
#     print("Weight:", knapsack_weight[x].w)
#     print()

# print("=====================================")
# print("Sorted by Value")
# for x in range(len(knapsack_value)): 
#     print("Knapsack", knapsack_value[x].i,":")
#     print("Value:", knapsack_value[x].v)
#     print("Weight:", knapsack_value[x].w)
#     print()

# print("=====================================")
# print("Sorted by Density")
# for x in range(len(knapsack_density)): 
#     print("Knapsack", knapsack_density[x].i,":")
#     print("Value:", knapsack_density[x].v)
#     print("Weight:", knapsack_density[x].w)
#     print("Ratio:", ratio(knapsack_density[x]))
#     print()
#Ambil item berdasarkan density
W_density = 0
V_density = 0
taken_density = []

for x in range(len(knapsack_density)):
  if W_density+knapsack_density[x].w > int(W_max):
    break
  taken_density.append(knapsack_density[x]);
  W_density += knapsack_density[x].w
  V_density += knapsack_density[x].v
  
#Print knapsack yang diambil, value yang didapat, dan weight yang didapat
print('Greedy by Density')
print('Banyak knapsack yang diambil:', len(taken_density))
print('Value:',V_density)
print('Weight:', W_density)
print()
print('Knapsack yang diambil:')
for x in range(len(taken_density)): 
    print("Knapsack", taken_density[x].i,":")
    print("Value:", taken_density[x].v)
    print("Weight:", taken_density[x].w)
    print()
#Ambil item berdasarkan weight
W_weight = 0
V_weight = 0
taken_weight = []

for x in range(len(knapsack_weight)):
  if W_weight+knapsack_weight[x].w > int(W_max):
    break
  taken_weight.append(knapsack_weight[x]);
  W_weight += knapsack_weight[x].w
  V_weight += knapsack_weight[x].v
  
#Print knapsack yang diambil, value yang didapat, dan weight yang didapat
print('Greedy by Weight')
print('Banyak knapsack yang diambil:', len(taken_weight))
print('Value:',V_weight)
print('Weight:', W_weight)
print()
print('Knapsack yang diambil:')
for x in range(len(taken_weight)): 
    print("Knapsack", taken_weight[x].i,":")
    print("Value:", taken_weight[x].v)
    print("Weight:", taken_weight[x].w)
    print()
#Ambil item berdasarkan value
W_value = 0
V_value = 0
taken_value = []

for x in range(len(knapsack_value)):
  if W_value+knapsack_value[x].w > int(W_max):
    break
  taken_value.append(knapsack_value[x]);
  W_value += knapsack_value[x].w
  V_value += knapsack_value[x].v
  
#Print knapsack yang diambil, value yang didapat, dan weight yang didapat
print('Greedy by Value')
print('Banyak knapsack yang diambil:', len(taken_value))
print('Value:',V_value)
print('Weight:', W_value)
print()
print('Knapsack yang diambil:')
for x in range(len(taken_value)): 
    print("Knapsack", taken_value[x].i,":")
    print("Value:", taken_value[x].v)
    print("Weight:", taken_value[x].w)
    print()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.2017051362029528, 'fraction_numerical': 0.004158868787689748, 'mean_word_length': 5.387782204515272, 'pattern_counts': {'":': 9, '<': 6, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '530862', 'license': 'MIT', 'n_tokens_mistral': 1848, 'n_tokens_neox': 1766, 'n_words': 345, 'path': '0-1 Knapsack Greedy Algorithm.ipynb', 'repo_name': 'catlaughing/3-ways-for-knapsack', 'size': '4829'}