题目描述
01背包的至少问题
此题要求氧气和氮气的含量”至少是”j。
f(i,j,k)因为是”至少”，所以体积j和k可以为负数，当体积为正数的时候得到的答案，肯定也满足”至少是”负数，
因此，此题体积为负数时的状态也是有意义的，也要转移过来。
附：至多，恰好，至少的分析方法
至多：
全部初始化为0，保证V>=0;
恰好：
f0初始化为0，其余为正无穷。保证V>=0;
至少：
f0初始化为0，其余为正无穷。
二刷：再次深入辨析恰好、至多、至少
1. 恰好
如01背包中，若是恰好体积为v时，价值的最大值，把f[0]=0，其余等于负无穷
因为此处j是从m开始遍历，一直–，直到减到vi
这里更新时，如第一个物品体积是5，价值是10，除了f[5]，其余的做f[j]=max(f[j],f[j-v[i]+w[i])都是负无穷，不合法，因此实现了“恰好”
2. 至多
至多就是常规的做法，01背包，体积至多是v的最大价值
3. 至少
用题中的原物品和原物品的同等花费的一部分 去进行”恰好“做法 ，得到的f[n][m] 即为恰好氧气为n 氮气为m的最小花费
总结： 用原物品与原物品的部分 去进行恰好做法 就是 至少 做法
意思就是，在代价（体积）与原物体相同的情况下，价值比原物体小的集合，也要更新
初始化
关于初始化，如果问题求最大，则初始化为负无穷；最小则初始化为正无穷
#include <iostream>
#include <cstring>
using namespace std;
const int N=50,M=160;
//fijk表示，在前i个罐中拿，获得j氧气和k氮气时，最少的重量
int f[N][M];
int main()
{
int n,m;
cin>>n>>m;
int K;
cin>>K;
memset(f,0x3f,sizeof f);
f[0][0]=0;
while(K--)
{
int a, b, c;
cin >> a >> b >> c;
for (int i = n; i >= 0; i -- )
for (int j = m; j >= 0; j -- )
f[i][j] = min(f[i][j], f[max(0, i - a)][max(0, j - b)] + c);
}
cout<<f[n][m];
return 0;
}
二刷：需要注意的点如下：
- j和k要循环到0
#include <iostream>
#include <cstring>
using namespace std;
const int N=1010;
int f[N][N],o[N],d[N],v[N];
int main()
{
int need_o,need_n;
int n;
cin>>need_o>>need_n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>o[i]>>d[i]>>v[i];
}
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=need_o;j>=0;j--)
{
for(int k=need_n;k>=0;k--)
{
//体积至少为0,0时的代价，肯定是0，不会被右边更新
f[j][k]=min(f[j][k],f[max(j-o[i],0)][max(k-d[i],0)]+v[i]);
}
}
}
cout<<f[need_o][need_n];
return 0;
}
2023/11/27
简单复习了一下，有几个要点：
1. fijk: 从前i个罐子里选，氧气至少为j，氮气至少为k时所需的“最低”重量
本题是一个“至少为”问题，初始化方式：
1. 把所有值初始化为正无穷
2. f[0][0]=0， 意味什么都不取时所需重量为0
在循环时，fjk的更新方式：
f[j][k]=min(f[j][k],f[max(j-o2[i],0)][max(k-n2[i],0)]+m[i]);
注意这里，不能先判断，再进行更新
if(j>=o2[i) && k>=n2[i])
因为“至少为”的含义是：哪怕需要1个氧气，和1个氮气，即j-o2[i], j=1.
即使j-o2[i]<0了，也得加上一个m[i]的重量
#include <iostream>
#include <cstring>
using namespace std;
const int N=1010;
int n;
int no,nn;
int o2[N], n2[N], m[N];
// fijk: 从前i个罐子中拿，氧气至少为j，氮气至少为k时所需的最低重量
int f[N][N];
int main()
{
cin>>no>>nn;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>o2[i]>>n2[i]>>m[i];
}
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=no;j>=0;j--)
{
for(int k=nn;k>=0;k--)
{
f[j][k]=min(f[j][k],f[max(j-o2[i],0)][max(k-n2[i],0)]+m[i]);
}
}
}
cout<<f[no][nn];
return 0;
}
总结
“至少”的做法：
1. 把所有值初始化为正无穷
2. f[0][0]=0， 意味什么都不取时所需重量为0
3. 在循环中要把j-o2[i]<0的负值也更新
“恰好”的做法：
1. f0初始化为0，其余为正无穷。
2. 在循环中要严格保证j-o2[i]>=0, 不能更新负值
Yukino chan~