m0_73728530 2023-02-10 22:07 采纳率: 82.4%
浏览 38
已结题

贪心算法优化背包问题

贪心算法——背包问题
不是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))

改造前:

img

  • 写回答

2条回答 默认 最新

  • 社区专家-Monster-XH 2023-02-10 22:37
    关注

    基于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))
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 2月18日
  • 已采纳回答 2月10日
  • 创建了问题 2月10日

悬赏问题

  • ¥20 请问,这个视频播放软件的名称
  • ¥15 运筹优化,gurobi,python
  • ¥15 基于python的电影系统推荐
  • ¥20 springmvc重定向和返回json
  • ¥15 数学建模——参会安排怎么做
  • ¥15 电脑键盘实现触摸功能
  • ¥25 matlab无法将表达式转换为双数组怎么解决?
  • ¥15 单片机汇编语言相关程序
  • ¥20 家用射频美容仪技术规格
  • ¥15 大家帮我看看为什么错了