贪心算法优化背包问题

Question

贪心算法——背包问题
不是0-1背包 可以一个物品多拿几次。以下代码如何改造一下。
--------------*改造后应该是：带4个6kg（体积）的，总共的最大利润是￥480-*---------------------------

#各物品的体积列表
v = [2,8,5,6,15,3,7]
#各物品的价值列表
val = [30,100,10,120,280,50,40]
#各物品编号
num = [1,2,3,4,5,6,7]
#各物品价格/体重
v_val = []
#输入背包体积
VS = 25
#输入物品种类数
S = 7

#计算价格与体重之比
for i in range(S):
    v_val.append(val[i]/v[i])
#排序
for i in range(S):
    for j in range(i+1,S):
        if v_val[i] < v_val[j]:
            v_val[i],v_val[j] = v_val[j],v_val[i]
            v[i],v[j] = v[j],v[i]
            val[i],val[j] = val[j],val[i]
            num[i],num[j] = num[j],num[i]

print("编号：{}".format(num))
print("体积：{}".format(v))
print("价值：{}".format(val))

#不可分割物品
#当前背包占用体积
v1_now = 0
#当前背包内价值
val1_now = 0

print("背包内加入的物品编号有：",end='')
for i in range(S):
    if (v[i] + v1_now) <= VS:
        v1_now +=v[i]
        val1_now += val[i]
        print(num[i],end='')
    else:
        break
print()
#背包占用体积为
print("背包体积:{}".format(v1_now))
print("背包价值:{}".format(val1_now))

改造前：

Answer 1

基于Monster 组和GPT的调写：
可以在代码中增加一个循环，在每次放入背包之前判断是否有余地，如果有余地则再次放入。代码如下

v = [2,8,5,6,15,3,7]
val = [30,100,10,120,280,50,40]
num = [1,2,3,4,5,6,7]
v_val = []
VS = 25
S = 7
 
for i in range(S):
    v_val.append(val[i]/v[i])
 
for i in range(S):
    for j in range(i+1,S):
        if v_val[i] < v_val[j]:
            v_val[i],v_val[j] = v_val[j],v_val[i]
            v[i],v[j] = v[j],v[i]
            val[i],val[j] = val[j],val[i]
            num[i],num[j] = num[j],num[i]
 
print("编号：{}".format(num))
print("体积：{}".format(v))
print("价值：{}".format(val))
 
v1_now = 0
val1_now = 0
 
print("背包内加入的物品编号有：",end='')
for i in range(S):
    while (v[i] + v1_now) <= VS:
        v1_now += v[i]
        val1_now += val[i]
        print(num[i],end='')
    if v1_now == VS:
        break
print()
print("背包体积:{}".format(v1_now))
print("背包价值:{}".format(val1_now))