-----本题解中,使用“大于等于”来描述状态-----
问题建模
有n个罐子,每个罐子有三个属性:氧量、氮量、重量,求解将哪些罐子放入背包可以使得在满足
“总氧量 >= 需要的氧量 且 总氮量 >= 需要的氮量”的情况下罐子的总重量最小
分析
在01背包问题中我们需要考虑两个东西:价值和代价
在最简单的01背包中题目是求在“总体积<=V”时能得到的最大值
在本题中,题目要求“总氧量 >= 需要的氧量 且 总氮量 >= 需要的氮量”时重量的最小值,故在本题中每个物品(罐子)的代价为(1)氧量(2)氮量,价值为重量
闫氏DP分析法:状态表示 and 计算
定义f[i][j][k]=“从前i个罐子中选择若干罐子,在罐子的总氧量 >= 需要的氧量 且 总氮量 >= 需要的氮量情况下能获得的最小重量
显然,根据选or不选第i个罐子我们可以分为两种情况
(1)不选:则f[i][j][k] = f[i-1][j][k]
(2)选:f[i][j][k] = f[i-1][j- a[i] ][k - b[i] ] + c[i],其中a[i],b[i],c[i]分别表示第i个罐子的氧量、氮量、重量。
当j < a[i] 或 k < b[i]
按普通的01背包的思想,我们会要求执行f[i-1][j- a[i] ][k - b[i]]时j >= a[i] and k >= b[i],但是本题对状态f[i][j][k]的定义同普通01背包不同,它是“不超过V(即<=V)”而本题是“总氧量 >= 需要的氧量 且 总氮量 >= 需要的氮量(对应到普通01中就是不小于V)”
从实际含义出发,例如,假设i=2,j=3,k=4,a[i]=10,b[i]=10,我们知f[2][3][4]表示“从前2个选,总氧量>=3,总氮量>=4时重量最小值”,由于第2个罐子本身的氧量>3、氮量>4,因此当选第2个时,就不再需要选别的罐子(因为它一个就可以满足要求且题目规定罐子重量>=1),即此时应该令f[i-1][j-a[i]][k-b[i]]=0,
为了更好的处理这种情况,可以把状态转移方程改为f[i-1][max(0, j - a[i])][max(0, k - b[i])],当出现上面这种情况时转移方程等价于f[i-1][0]0;否则,它等价于f[i-1][j-a[i]][k-b[i]],因此,经过max()处理后我们的状态转移方程在没有改变与原转移方程等价的情况下还能处理负数下标
初始化
根据对f[i][j][k]的定义有
(1)、f[0][0][0] = 0
(2)、f[x][0][0] = 0(x = 1,2,3,…,k),同(1)一样,由于j=k=0,因此我们可以不选任何罐子
(3)、当j、k不全为0,f[0][j][k] = 无穷大,这是非法状态
(4)、对于其他的非法状态,全部初始化为无穷大
Python朴素版O(mnk)
INF = 0x3f3f3f3f
M, N, K = 28,88,1010
m, n = map(int, input().split())
k = int(input())
a, b, c = [0] * K, [0] * K, [0] * K
for i in range(1, 1 + k):a[i], b[i], c[i] = map(int, input().split())
f = [[[INF for i in range(N)] for i in range(M)] for i in range(K)]
for i in range(k + 1): f[i][0][0] = 0
for i in range(1, 1 + k):
for j in range(0, 1 + m):
for kk in range(0, 1 + n):
f[i][j][kk] = min(f[i - 1][j][kk], c[i] + f[i - 1][max(0, j - a[i])][max(0, kk - b[i])])
print(f[k][m][n])
请注意,第2、3层循环需要从0开始,从实际含义出发,因为f[i][0][k]和f[i][j][0]是合法状态,需要进行处理
优化
M, N, K = 28,88,1010
m, n = map(int, input().split())
k = int(input())
a, b, c = [0 for i in range(K)], [0 for i in range(K)], [0 for i in range(K)]
for i in range(1, 1 + k): a[i], b[i], c[i] = map(int, input().split())
f = [[0x3f3f3f3f for i in range(N)] for i in range(M)]
f[0][0] = 0
#根据普通01背包滚动数组进行优化
for i in range(1, 1 + k):
for j in range(m, -1, -1):#大到小
for kk in range(n, -1, -1):#大到小
f[j][kk] = min(f[j][kk], f[max(0, j - a[i])][max(0, kk - b[i])] + c[i])
print(f[m][n])