背包类题型

//二维费用的01背包，值得注意的是 我们平常做题时，费用可以为0，即是范围为0~v
//，本题限制了费用不能为0，即范围是1~v那么我们只需要改变一下范围就好了即
//变为 0~v-1  就可以直接套用模板了
#include
using namespace std;
int n,m,k;
int use[1010],hurt[1010];
int f[1010][510];
int main(){
    cin >> m >> k >> n;//精灵球数量 ,生命值,精灵个数
    for(int i=1;i<=n;i++){
        cin >> use[i] >> hurt[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=use[i];j--){
            for(int l=k-1;l>=hurt[i];l--){
                f[j][l]=max(f[j-use[i]][l-hurt[i]]+1,f[j][l]);
                ans=max(ans,f[j][l]);
            }
        }
    }
    int res=INT_MAX;
    for(int l=0;l<=k-1;l++){
        if(ans==f[m][l])
        {
        res=min(res,l);
    }
        
    }
    cout << ans << " " < 
潜水员 
//二维费用求至少值的01背包问题
#include
using namespace std;
const int N=1010;
int m,k,n;
int o2[N],n2[N],w[N];
int f[150][150];//f[i][j]表示氧气至少为i氮气至少为j的所能带的最小重量
int main(){
    cin >> m >> k >> n;
    memset(f,0x3f,sizeof f);//给这个数组中不合理的数据进行无效化，使得在转业的过程中取不到
    for(int i=1;i<=n;i++){
        cin >> o2[i] >> n2[i] >> w[i];
    }
    f[0][0]=0;//f[0][0]是唯一合理的
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            for(int l=k;l>=0;l--){
                f[j][l]=min(f[j][l],f[max(0,j-o2[i])][max(0,l-n2[i])]+w[i]);
            }
        }
    }
    cout << f[m][k] << endl;
    return 0;
}
 
背包求最值三种情况:（以下情况状态转移方程都一样）
 1.求最大值则 初始化f数组全为0，且状态转移中要保证v始终>=0
 2.求至少值或者至多为初始化数组全为正无穷或者负无穷（根据dp表示的具体含义来看），本题中求的是至少则初始化为正无穷，但是v在状态转移过程中可以小于0，例如f[-5]假如表示氧气至少为-5 的所有集合中重量最小的,
 具体到问题中的体现就是for循环过程中j>=0,而另两种情况为j>=v[i]。
 3.求恰好，状态初始化与第二种情况相同，且状态转移过程中要保证v始终>=0，
 
就本题而言 可做如下分析：
 对于“考虑前i个物品，氧气体积大于等于j，氮气体积大于等于k的方案”的集合（f[i][j][k]）
 可以按照“是否选择第i个物品”来划分
 若不选择第i个物品
 则就是“考虑前i-1个物品，氧气体积大于等于j 并且氮气体积大于等于k的方案”的集合 (f[i-1][j][k])
 若选择了第i个物品
 由于该集合均包含第i个物品
 假设第i个物品有v1个氧气 v2个氮气
 则除去第i个物品
 就是考虑“从前i-1个物品选 氧气体积大于等于j-v1 氮气体积大于等于k-v2的方案”的集合
 若j-v1小于零的话
 就说明第i个物品提供的氧气已经足够
 不需要从前i-1个物品中获得任何氧气
 因此当j-v1小于零的时候
 直接按照0考虑即可
 氮气也一样
 
摘自作者：铃兰的顶点
 链接：https://www.acwing.com/video/379/
 来源：AcWing
 相关参考资料
 
 

 参考分享来源