背包问题 python 背包九讲

基础：01背包

t,m=list(map(int,input().split()))
baowu=[None]
ditu=[[0]*(t+1) for _ in range(m+1)]
for i in range(m):
    a1,a2=list(map(int, input().split()))
    baowu.append({'w':a1,'v':a2})
ditu2=[0]*(t+1)
for i in range(1,m+1):
    #for w in range(1, t + 1):
#原始
    #     if baowu[i]['w']>w:
    #         ditu[i][w]=ditu[i-1][w]
    #     else:
    #         ditu[i][w] =max(ditu[i-1][w],ditu[i-1][w-baowu[i]['w']]+baowu[i]['v'])
#一维优化
    for j in range(t,baowu[i]['v']-1,-1):
        ditu2[j]=max( ditu2[j], ditu2[j-baowu[i]['w']]+baowu[i]['v'])


# print(ditu[m][t])
print(ditu2[t])

P1060 [NOIP2006 普及组] 开心的金明

P1060 [NOIP2006 普及组] 开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

t,m=list(map(int,input().split()))
baowu=[None]
ditu=[[0]*(t+1) for _ in range(m+1)]
for i in range(m):
    a1,a2=list(map(int, input().split()))
    baowu.append({'w':a1,'v':a2})
ditu2=[[0,0]]*(t+1)
for i in range(1,m+1):
    for j in range(t,0,-1):
        if baowu[i]['w']<=j:#是否装得下
            if ditu2[j][1]>=ditu2[j-baowu[i]['w']][1]+baowu[i]['v']*baowu[i]['w']:#比较拿和不拿的价值
                ditu2[j]=ditu2[j]
            else:
                ditu2[j]=[ditu2[j-baowu[i]['w']][0]+baowu[i]['v'],ditu2[j-baowu[i]['w']][1]+baowu[i]['v']*baowu[i]['w']]
print(ditu2[t][1])

一维优化

01背包 找路径

【Python算法系列】动态规划2-01背包问题&完全背包问题_哔哩哔哩_bilibili

完全背包