二维费用01背包(Python)

# 题目来源ACM训练系统 第3056题

# 01背包

# 1.获取数据

n,m,k=map(int,input().split())

list1=[]

for i in range(k):

    list1.append(list(map(int,input().split())))

list1.insert(0,[0,0]) # 题目不会用到下标为0的数据 随意就行

num=len(list1)

# 2.定义dp数组和初始化(采用滚动数组)

dp=list([0]*(m+1) for i in range(n+1))

for i in range(1,num):

    for j in range(n,list1[i][0]-1,-1):

        for k in range(m,list1[i][1]-1,-1):

            dp[j][k]=max(dp[j][k],dp[j-list1[i][0]][k-list1[i][1]]+1)

# 3.输出结果

listx=dp[n]

print(dp[n][m],m-listx.index(dp[n][m]))

"""

1.当然咱们做题不能仅限此题,如果是完全背包要怎么修改代码呢？

2.只需要把倒叙遍历改回正序遍历就行啦！

dp=list([0]*(m+1) for i in range(n+1))

for i in range(1,num):

    for j in range(list1[i][0],n+1):

        for k in range(list1[i][1],m+1):

            dp[j][k]=max(dp[j][k],dp[j-list1[i][0]][k-list1[i][1]]+1)

"""