栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

python背包问题

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

python背包问题

背包问题可以分为:01背包 和 完全背包问题。

简要概括:

01背包:每种物品只能拿一次或者不拿。

完全背包:每种物品可以拿无限次。

01背包:

import numpy as np
weight=[1,3,6,5,7]           #物品重量
price=[2,1,3,5,4]            #物品价值
weight_most=10
def fullbag(weight,price,weight_most):#return max value
    num = len(weight)        #获取物品总量
    weight.insert(0,0)      #不存在第0个物品,故插入一个0
    price.insert(0,0)        #同上
    bag=np.zeros((num+1,weight_most+1),dtype=np.int32)#使用numpy快速建立数组,下标从零开始
#     bag0 = [0 for j in range(weight_most+1)]          #不导入np三方库
#     bag = [bag0 for i in range(num+1)]

    for i in range(1,num+1):     #这俩循环的取值为行与列,每件物品进行循环
        for j in range(1,weight_most+1):       #从轻的开始拿
            if weight[i]<=j:
                bag[i][j]=max(bag[i-1][j-weight[i]]+price[i],bag[i-1][j])
            else:
                bag[i][j]=bag[i-1][j]
    print(bag)
    return bag[-1,-1]
 
result=fullbag(weight,price,weight_most)
print(result)
解法来源:https://blog.csdn.net/your_answer/article/details/79274789

完全背包:

import numpy as np
weight=[1,3,6,5,7]           #物品重量
price=[2,1,3,5,4]            #物品价值
weight_most=10
def fullbag(weight,price,weight_most):#return max value
    num = len(weight)        #获取物品总量
    weight.insert(0,0)      #不存在第0个物品,故插入一个0
    price.insert(0,0)        #同上
    bag=np.zeros((num+1,weight_most+1),dtype=np.int32)#使用numpy快速建立数组,下标从零开始
#     bag0 = [0 for j in range(weight_most+1)]          #不导入np三方库
#     bag = [bag0 for i in range(num+1)]

    for i in range(1,num+1):     #这俩循环的取值为行与列,每件物品进行循环
        for j in range(1,weight_most+1):       #从轻的开始拿
            if weight[i]<=j:
                bag[i][j]=max(bag[i-1][j-weight[i-1]]+price[i-1],bag[i-1][j])
            else:
                bag[i][j]=bag[i-1][j]
    print(bag)
    return bag[-1,-1]
 
result=fullbag(weight,price,weight_most)
print(result)

该博主为完全背包提供了更多的解法:

完全背包问题(python实现)的几种解法,动态规划_路漫漫`的博客-CSDN博客_python完全背包动态规划

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/892710.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号