动态规划——二维费用的背包问题-创新互联

背包的限制条件有两个，此时我们直接加上一重循环即可。注意二维限制可以加在任意类型的背包问题上。

例题：

有 N 件物品和一个容量是 V 的背包，背包能承受的大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

输出大价值。

输入格式：

第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的大重量。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式：

输出一个整数，表示大价值。

思路：

该题为二维费用的01背包。f[i][j][k]表示前i个物品，背包体积为j，承重为k的时候的大价值。在01背包基础上加上一重循环即可。由于n*3的空间太大，所以我们直接使用优化后的01背包。

代码如下：

#includeusing namespace std;

int f[1010][1010];
int N, V, M;

int main() {
    cin >>N >>V >>M;

    int v, m, w;
    for (int i = 0; i< N; i++) {
        cin >>v >>m >>w;
        for (int j = V; j >= v; j--)
            for (int k = M; k >= m; k--)
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    }

    cout<< f[V][M];

    return 0;

}

小智想收服一些小精灵。

对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害。

当皮卡丘的体力小于等于0或者精灵球用完时，小智就必须结束狩猎。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小。

输入格式：

输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

输出格式：

输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

二维的01背包问题，像普通01背包一样做就行，只是加一层循环。最后输出f[n][m]（n个球，m个体力）。要输出剩下的体力值，我们遍历f[n][0]~f[n][m]即可。

题目要求当体力为0的时候算抓捕失败，所以我们把m-1当做m带入计算即可。

代码如下：

#includeusing namespace std;
const int N=1010;
int f[N][N];
int n,m,k;//拥有的球数和体力值、精灵数
int main(){
    cin>>n>>m>>k;
    int a,b;//每只精灵需要的球数和照成的伤害
    for(int i=0;i>a>>b;
        for(int j=n;j>=a;j--)//遍历球数
            for(int u=m-1;u>=b;u--)//遍历体力
                f[j][u]=max(f[j][u],f[j-a][u-b]+1);
    }
    
    int tmp=0;
    for(int i=m;i>=0;i--)
        if(f[n][i]==f[n][m-1])tmp=i;
        
    cout<

f[i][j][k] = f[i - 1][j - o2[i]][k - n2[i]]

f[i][j][k] = f[i - 1][j][k]。

#include#includeusing namespace std;

const int N = 1010;
int f[N][N];//o2,n2
int n, m;//o2,n2

int main() {
    cin >>n >>m;
    int s, o2, n2, m2;
    cin >>s;

    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 0; i< s; i++) {
        cin >>o2 >>n2 >>m2;
        for (int j = n; j >= 0; j--)
            for (int k = m; k >= 0; k--)
                f[j][k] = min(f[j][k], f[max(j - o2, 0)][max(k - n2, 0)] + m2);
    }

    cout<< f[n][m];

    return 0;
}