题目描述

三维背包问题

注意此题一定要空间优化（优化掉i，即第i个小精灵抓不抓那一维），不然会爆空间！！

#include <iostream>

using namespace std;

const int N=1010;

int sp[N],dm[N],f[502][1002];

int main()
{
    int n,m,k;
    //精灵球，体力，野怪
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    {
        cin>>sp[i]>>dm[i];
    }
    //目的：收服最多的小精灵，且m剩的越多越好
    //fijh表示在第i个野怪之前，体力还剩j，精灵球还剩h，收服的小精灵数量

    for(int i=1;i<=k;i++)
    {
        for(int j=m;j>=1;j--)
        {
            for(int h=n;h>=1;h--)
            {
                //逃跑
                f[j][h]=f[j][h];
                if(h>=sp[i] && j>dm[i])
                {
                    f[j][h]=max(f[j][h],f[j-dm[i]][h-sp[i]]+1);
                }
            }
        }
    }

    int res=f[m][n];

    int hp;
    if(res==0)
    cout<<0<<" "<<100;

    else
    {
        for(int i=m;i>=1;i--)
        {
            if(f[i][n]!=res)
            {
                hp=i;
                break;
            }
        }
        cout<<res<<" "<<m-hp;
    }



    return 0;
}

2023/11/27

三维背包，需要维度优化，不然会空间不足
还需要特判的是，不能让皮卡丘死了，即剩余hp=0

有一个坑，很重要

在做维度优化时，循环里一定要遍历到0，不能遍历到v[i]

    for(int i=1;i<=n;i++)
    {
        for(int j=hp;j>=0;j--)
        {
            for(int k=m;k>=0;k--)
            {
                if(j >= d[i] && k >= v[i])
                {
                    f[j][k] = max(f[j][k], f[j-d[i]][k-v[i]] + 1);
                }
            }
        }
    }

内层循环不能写成：必须遍历到0

    for(int i=1;i<=n;i++)
    {
        for(int j=hp;j>=d[i];j--)
        {
            for(int k=m;k>=v[i];k--)
            {
                if(j >= d[i] && k >= v[i])
                {
                    f[j][k] = max(f[j][k], f[j-d[i]][k-v[i]] + 1);
                }
            }
        }
    }

#include <iostream>

using namespace std;



int n,m,hp;
// f[i][j][k]:
// 从前i个精灵里面抓，体力不超过j，精灵球不超过k
int f[510][1010];
int v[110],d[110];

int main()
{
    cin>>m>>hp>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>d[i];
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=hp;j>=0;j--)
        {
            for(int k=m;k>=0;k--)
            {
                if(j >= d[i] && k >= v[i])
                {
                    f[j][k] = max(f[j][k], f[j-d[i]][k-v[i]] + 1);
                }
            }
        }
    }



    int res = f[hp][m];
    int max_hp = 0;

    for(int j=0;j<=hp;j++)
    {
        if(f[j][m] == res)
        {
            max_hp = hp -j;
            break;
        }
    }

    // 如果皮卡丘死了 
    if(max_hp == 0)
    {
        res = res-1;

    }

    for(int j=0;j<=hp;j++)
    {
        if(f[j][m] == res)
        {
            max_hp = hp -j;
            break;
        }
    }

    cout<<res<<" "<<max_hp;


    return 0;
}