请帮我解决分数背包问题（战利品的最大值）
Please help me in solving Fractional Knapsack problem (Maximum Value of the Loot)
战利品的最大值
Problem Introduction:
A thief finds much more loot than his bag can fit. Help him to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag.
Problem Description
Task: The goal of this code problem is to implement an algorithm for the fractional knapsack problem.
Input Format: The first line of the input contains the number of items and the capacity of a knapsack. The next lines define the values and weights of the items. The -th line contains integers and —the value and the weight of -th item, respectively.
Constraints: 1≤≤103,0≤ ≤2·106;0≤ ≤2·106,0< ≤2·106 for all 1≤≤.All the numbers are integers.
Output Format Output the maximal value of fractions of items that fit into the knapsack. The absolute value of the difference between the answer of your program and the optimal value should be at most
−3
your answer, while being computed correctly, can turn out to be wrong because of rounding issues).
样本 1.
输入：
3 50
60 20
100 50
120 30
输出：
180.0000
为了达到180的价值，我们将第一项和第三项放入包中。
样本 2.
输入：
1 10
500 30
输出：
166.6667
我的代码：
# Maximum Value of the Loot
def knapsack(n, capacity, value_list, weight_list):
unitValues_list = []
#First lets calculate the unitValues_list
for i in range (n):
unitValue = (value_list[i]/weight_list[i])
unitValues_list.append(unitValue)
#Now lets fill the knapsack, intake is how much is in the bag at the moment!
intake = 0
max_value = 0
factor = True
while(factor):
max_index = unitValues_list.index(max(unitValues_list, default=0))
# this gives the index of the max valued element
if(weight_list[max_index] <= capacity):
# In this case, full item is taken in
intake = weight_list[max_index]
capacity -= weight_list[max_index]
max_value += value_list[max_index]
else:
# weight_list[max_index] > capacity
# In this case, fraction to be taken
intake += capacity
capacity = 0
max_value += unitValues_list[max_index]*intake
weight_list.pop(max_index)
value_list.pop(max_index)
unitValues_list.pop(max_index)
print(weight_list)
n -= 1 #no. of items left
factor = ((n != 0) if ((capacity != 0) if True else False) else False)
return max_value
if __name__ == "__main__":
value_list = []
weight_list = []
#The first line of the input contains the number of items and the capacity of a knapsack.
#The next lines define the values and weights of the items.
n , capacity = map(int, input().split())
for i in range (n):
value , weight = map(int, input().split())
value_list.append(value)
weight_list.append(weight)
#Output the maximal value of fractions of items that fit into the knapsack.
print("{:.10f}".format(knapsack(n, capacity, value_list, weight_list)))
我一直收到错误消息：
失败案例 #6/13：答案错误
得到：8740.3008948546 预期：7777.731
（使用时间：0.00/5.00，使用内存：9191424/671088640。）
更正错误答案
通过改变
得到的更正分数
intake += capacity
capacity = 0
max_value += unitValues_list[max_index]*intake
到
fraction = capacity / weight_list[max_index]
max_value += value_list[max_index]*fraction
capacity = 0
重构代码
def knapsack(n, capacity, value_list, weight_list):
unitValues_list = []
#First lets calculate the unitValues_list
for i in range (n):
unitValue = (value_list[i]/weight_list[i])
unitValues_list.append(unitValue)
#Now lets fill the knapsack, intake is how much is in the bag at the moment!
intake = 0
max_value = 0
factor = True
while(factor):
max_index = unitValues_list.index(max(unitValues_list, default=0))
# this gives the index of the max valued element
if(weight_list[max_index] <= capacity):
# In this case, full item is taken in
intake = weight_list[max_index]
capacity -= weight_list[max_index]
max_value += value_list[max_index]
else:
# weight_list[max_index] > capacity
# In this case, fraction to be taken
fraction = capacity / weight_list[max_index]
max_value += value_list[max_index]*fraction
capacity = int(capacity - (weight_list[max_index] * fraction))
weight_list.pop(max_index)
value_list.pop(max_index)
unitValues_list.pop(max_index)
print(weight_list)
n -= 1 #no. of items left
factor = ((n != 0) if ((capacity != 0) if True else False) else False)
return max_value
if __name__ == "__main__":
value_list = []
weight_list = []
#The first line of the input contains the number of items and the capacity of a knapsack.
#The next lines define the values and weights of the items.
n , capacity = map(int, input('n, capacity: ').split())
for i in range (n):
value , weight = map(int, input('value, weight: ').split())
value_list.append(value)
weight_list.append(weight)
#Output the maximal value of fractions of items that fit into the knapsack.
print("{:.10f}".format(knapsack(n, capacity, value_list, weight_list)))
备注
没有提到时间问题。
通过排序 unitValues_list 而不是每次计算最大值，可以将复杂度从当前的 O(n^2) 算法更改为 O(n*log(n))。
这是战利品问题的解决方案。按照贪心算法，我们从单价最高的项目开始填充..
def loot(t_weight,cost, unit,weight):
count = 0
while t_weight!=0:
c_cost = max(unit)
act_ind = unit.index(c_cost)
c_weight=weight[act_ind]
print(c_cost,c_weight,act_ind)
if c_weight >= t_weight:
count+=t_weight*c_cost
t_weight = 0
elif c_weight<t_weight:
t_weight-=c_weight
count+=(c_weight)*c_cost
cost.pop(act_ind)
unit.pop(act_ind)
weight.pop(act_ind)
print()
return count
def main():
g1=str(input())
item,cap = map(int,g1.split())
dict={}
cost=[]
weight=[]
unit =[]
for i in range(1,item+1):
g2=str(input())
a,b = map(int,g2.split())
cost.append(a)
weight.append(b)
j = (cost[i-1])/weight[i-1]
unit.append(j)
print(loot(cap,cost,unit,weight))
main()
战利品的最大值
Problem Introduction:
A thief finds much more loot than his bag can fit. Help him to find the most valuable combination of items assuming that any fraction of a loot item can be put into his bag. Problem Description
Task: The goal of this code problem is to implement an algorithm for the fractional knapsack problem.
Input Format: The first line of the input contains the number of items and the capacity of a knapsack. The next lines define the values and weights of the items. The -th line contains integers and —the value and the weight of -th item, respectively.
Constraints: 1≤≤103,0≤ ≤2·106;0≤ ≤2·106,0< ≤2·106 for all 1≤≤.All the numbers are integers.
Output Format Output the maximal value of fractions of items that fit into the knapsack. The absolute value of the difference between the answer of your program and the optimal value should be at most −3 your answer, while being computed correctly, can turn out to be wrong because of rounding issues).
样本 1.
输入：
3 50
60 20
100 50
120 30
输出：
180.0000
为了达到180的价值，我们将第一项和第三项放入包中。
样本 2.
输入：
1 10
500 30
输出：
166.6667
我的代码：
# Maximum Value of the Loot
def knapsack(n, capacity, value_list, weight_list):
unitValues_list = []
#First lets calculate the unitValues_list
for i in range (n):
unitValue = (value_list[i]/weight_list[i])
unitValues_list.append(unitValue)
#Now lets fill the knapsack, intake is how much is in the bag at the moment!
intake = 0
max_value = 0
factor = True
while(factor):
max_index = unitValues_list.index(max(unitValues_list, default=0))
# this gives the index of the max valued element
if(weight_list[max_index] <= capacity):
# In this case, full item is taken in
intake = weight_list[max_index]
capacity -= weight_list[max_index]
max_value += value_list[max_index]
else:
# weight_list[max_index] > capacity
# In this case, fraction to be taken
intake += capacity
capacity = 0
max_value += unitValues_list[max_index]*intake
weight_list.pop(max_index)
value_list.pop(max_index)
unitValues_list.pop(max_index)
print(weight_list)
n -= 1 #no. of items left
factor = ((n != 0) if ((capacity != 0) if True else False) else False)
return max_value
if __name__ == "__main__":
value_list = []
weight_list = []
#The first line of the input contains the number of items and the capacity of a knapsack.
#The next lines define the values and weights of the items.
n , capacity = map(int, input().split())
for i in range (n):
value , weight = map(int, input().split())
value_list.append(value)
weight_list.append(weight)
#Output the maximal value of fractions of items that fit into the knapsack.
print("{:.10f}".format(knapsack(n, capacity, value_list, weight_list)))
我一直收到错误消息：
失败案例 #6/13：答案错误
得到：8740.3008948546 预期：7777.731
（使用时间：0.00/5.00，使用内存：9191424/671088640。）
更正错误答案
通过改变
得到的更正分数intake += capacity
capacity = 0
max_value += unitValues_list[max_index]*intake
到
fraction = capacity / weight_list[max_index]
max_value += value_list[max_index]*fraction
capacity = 0
重构代码
def knapsack(n, capacity, value_list, weight_list):
unitValues_list = []
#First lets calculate the unitValues_list
for i in range (n):
unitValue = (value_list[i]/weight_list[i])
unitValues_list.append(unitValue)
#Now lets fill the knapsack, intake is how much is in the bag at the moment!
intake = 0
max_value = 0
factor = True
while(factor):
max_index = unitValues_list.index(max(unitValues_list, default=0))
# this gives the index of the max valued element
if(weight_list[max_index] <= capacity):
# In this case, full item is taken in
intake = weight_list[max_index]
capacity -= weight_list[max_index]
max_value += value_list[max_index]
else:
# weight_list[max_index] > capacity
# In this case, fraction to be taken
fraction = capacity / weight_list[max_index]
max_value += value_list[max_index]*fraction
capacity = int(capacity - (weight_list[max_index] * fraction))
weight_list.pop(max_index)
value_list.pop(max_index)
unitValues_list.pop(max_index)
print(weight_list)
n -= 1 #no. of items left
factor = ((n != 0) if ((capacity != 0) if True else False) else False)
return max_value
if __name__ == "__main__":
value_list = []
weight_list = []
#The first line of the input contains the number of items and the capacity of a knapsack.
#The next lines define the values and weights of the items.
n , capacity = map(int, input('n, capacity: ').split())
for i in range (n):
value , weight = map(int, input('value, weight: ').split())
value_list.append(value)
weight_list.append(weight)
#Output the maximal value of fractions of items that fit into the knapsack.
print("{:.10f}".format(knapsack(n, capacity, value_list, weight_list)))
备注
没有提到时间问题。
通过排序 unitValues_list 而不是每次计算最大值，可以将复杂度从当前的 O(n^2) 算法更改为 O(n*log(n))。
这是战利品问题的解决方案。按照贪心算法，我们从单价最高的项目开始填充..
def loot(t_weight,cost, unit,weight):
count = 0
while t_weight!=0:
c_cost = max(unit)
act_ind = unit.index(c_cost)
c_weight=weight[act_ind]
print(c_cost,c_weight,act_ind)
if c_weight >= t_weight:
count+=t_weight*c_cost
t_weight = 0
elif c_weight<t_weight:
t_weight-=c_weight
count+=(c_weight)*c_cost
cost.pop(act_ind)
unit.pop(act_ind)
weight.pop(act_ind)
print()
return count
def main():
g1=str(input())
item,cap = map(int,g1.split())
dict={}
cost=[]
weight=[]
unit =[]
for i in range(1,item+1):
g2=str(input())
a,b = map(int,g2.split())
cost.append(a)
weight.append(b)
j = (cost[i-1])/weight[i-1]
unit.append(j)
print(loot(cap,cost,unit,weight))
main()