题目链接: https://www.acwing.com/problem/content/1022/
思路:
状态表示: f[i,j,k]:
所有从前i
个物品中选,且氧气含量至少是j
,氮气含量至少是k
的所有选法的气缸重量总和的最小值
集合划分: 选:f[i - 1][j][k]
不选: f[i - 1][j - v1][k - v2]
初始化:求最小值,初始化为INF
f[0][0][0] = 0
从实际意义出发,从前0
个物品中选,氧气含量 >= j
,氮气含量 >= k
的最小值为0。
可以抽象为:
状态表示: f[i,j,k]:
所有从前i
个物品中选,且体积至少是j
,重量至少是k
的所有选法的最小价值
集合划分: 选:f[i - 1][j][k]
不选: f[i - 1][j - v1][k - v2]
初始化:求最小值,初始化为INF
f[0][0][0] = 0
从实际意义出发,从前0
个物品中选,体积 >= j
,重量 >= k
的最小价值为0。
我们求至少需要的体积和重量,f[j][k]
表示至少需要j
个体积,k
个重量,对每一个物品i
的体积为v
,重量为m
如果选这个物品:
若j <= v
,则说明至少需要j
个体积等价于至少需要0
个体积
若k<=m
,则说明至少需要k
个重量等价于至少需要0
个重量
则有如下四种情况:
①j <= v && k <= m
②j <= v
③k <= m
④j >= v && k >= m
与朴素01背包不同的是:
普通的01二维背包:体积至多为j,重量至多为k
已经规定的容量为j和k,则取用物品的体积v和重量m:
j >= v && k >= m
此题的01二维背包:体积至少为j,重量至少为k
需要的容量为j和k,则取用物品的体积v和重量m
有容量小于取用物品容量的情况:
j <= v && k <= m
j <= v
k <= m
有容量都大于取用物品容量的情况:
j > v && k > m
对于最大值最小值初始化的总结:
二维情况
1、体积至多j
,f[i,k] = 0
,0 <= i <= n
, 0 <= k <= m
(只会求价值的最大值)
2、体积恰好j,
当求价值的最小值:f[0][0] = 0
, 其余是INF
当求价值的最大值:f[0][0] = 0
, 其余是-INF
3、体积至少j
,f[0][0] = 0
,其余是INF
(只会求价值的最小值)
一维情况
1、体积至多j
,f[i] = 0
, 0 <= i <= m
(只会求价值的最大值)
2、体积恰好j,
当求价值的最小值:f[0] =
0, 其余是INF
当求价值的最大值:f[0] = 0
, 其余是-INF
3、体积至少j
,f[0] = 0
,其余是INF
(只会求价值的最小值)
求方案数初始化总结
二维情况
1、体积至多j
,f[0][i] = 1
, 0 <= i <= m
,其余是0
2、体积恰好j
,f[0][0] = 1
, 其余是0
3、体积至少j
,f[0][0] = 1
,其余是0
一维情况
1、体积至多j
,f[i] = 1
, 0 <= i <= m
,
2、体积恰好j
,f[0] = 1
, 其余是0
3、体积至少j
,f[0] = 1
,其余是0
作者:小呆呆
总结参考链接: https://www.acwing.com/blog/content/458/
朴素代码如下:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50,S = 160;
int f[N][S];
int main()
{
int n,v,m;
cin>>v>>m>>n;
memset(f,0x3f,sizeof f);
f[0][0] = 0;
for(int i = 0;i < n;i++)
{
int a,b,w;
cin>>a>>b>>w;
for(int j = v;j >= 0;j--)
{
for(int k = m;k >= 0;k--)
{
if(j <= a && k <= b)
{
f[j][k] = min(f[j][k],f[0][0] + w);
}
else if(j <= a)
{
f[j][k] = min(f[j][k],f[0][k - b] + w);
}
else if(k <= b)
{
f[j][k] = min(f[j][k],f[j - a][0] + w);
}
else if(j > a && k > b)
{
f[j][k] = min(f[j][k],f[j - a][k - b] + w);
}
}
}
}
cout<<f[v][m]<<endl;
return 0;
}
对代码进行优化:
j <= a
: (j - a) <= 0
就选0
j > a
:(j - a) > 0
就选(j - a)
可得max(0,j - a)
同理可得max(0,k - b)
#include <iostream>
#include <cstring>
using namespace std;
const int N = 25,M = 80;
int f[N][M];
int main()
{
int m,n;
cin>>m>>n;
int k;
cin>>k;
memset(f,0x3f,sizeof f);
f[0][0] = 0;
for(int i = 0;i < k;i++)
{
int a,b,c;
cin>>a>>b>>c;
for(int j = m;j >= 0;j--)
{
for(int k = n;k >= 0;k--)
{
f[j][k] = min(f[j][k],f[max(0,j - a)][max(0,k - b)] + c);
}
}
}
cout<<f[m][n]<<endl;
return 0;
}