-
Notifications
You must be signed in to change notification settings - Fork 1
/
py02.py
99 lines (97 loc) · 2.87 KB
/
py02.py
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import numpy as np
import matplotlib.pyplot as plt
import random
import time
with open('idkp1-10.txt') as f:
allstr = f.readlines()
#print(allstr)
#读取组内数据
def func(s):
for i in range(len(allstr)):
if s in allstr[i]:
v1,v2 = allstr[i+1].split(',')
n=v1.split('=')[-1]
n=eval(n)
c=v2.split()[-1][:-1]
# print('diemnsion: ',n)
# print('cubage: ',c)
p = allstr[i+3].split(',')
v=p[:-1]
#print("物品的价值为:",p)
w = allstr[i+5].split(',')
w=w[:-1]
#print("物品的重量为:",w)
# print('\nprofit\t','weight')
# for n,m in zip(p,w):
# print(n,'\t',m)
# break
return n,c,v,w
#绘制重量——价值的散点图
def draw_scatter(n,v,w):
x=[]
y=[]
W=[]
V=[]
for i in range(n):
x=int(w[i])
W.append(x)
y=int(v[i])
v.append(y)
plt.scatter(x,y)
plt.title("W-V scatter plot")
plt.xlabel("W")
plt.ylabel("V")
plt.show()
#对价值与重量的比值进行非递增排序
def datasorted(w,v):
v_w=[]
v1=v[2::3]
w1=w[2::3]
for i in range(len(v1)):
s=int(v[i])/int(w[i])
v_w.append(s)
v_w.sort(reverse=True)
print(v_w)
def pack(w,v,C):
"""
w:list[list,list,...]
v:list[list,list,...]
"""
begin=time.time()
n_list = [3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
dp = [0 for _ in range(C + 1)]
for i in range(1, len(w) + 1): # 物品循环
for j in reversed(range(1, C + 1)): # 剩余体积循环
for k in range(n_list[i - 1]): # 别的和0,1背包一样 就是这里枚举一下每个组内的值,在每个组内选出一个max值
if j - w[i - 1][k] >= 0:
dp[j] = max(dp[j], dp[j - w[i - 1][k]] + v[i - 1][k])
#print("最大的价值为:",dp[C])
end=time.time()
t=end-begin
#print("运行时间为:",end-begin)
return dp[C],t
#n,c,v,w=func('IDKP0')
#n=eval(n)
if __name__=='__main__':
print("请输入你需要哪一组数据的文件:")
file=input()
n,c,v,w=func(file)
#print(n,c,v,w)
draw_scatter(n,v,w)
datasorted(w,v)
v1=[int(x)for x in v]
w1=[int(y)for y in w]
v2=[v1[i:i+3] for i in range(0, len(v1),3)] #3个3个分为一组
w2=[w1[i:i+3] for i in range(0, len(w1),3)] #3个3个分为一组
n1=len(v2)
#print(n1)
#print(v2,w2)
#print(v1[1][1],type(v1[1][1]))
C=int(c)
maxvalue,t=pack(w2,v2,C)
#print(t)
with open('结果.txt','w',encoding="utf-8") as f:
f.write("最大的价值为:")
f.write(str(maxvalue))
f.write("\n运行的时间为:")
f.write(str(t)+"S")