189 8069 5689

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

二维费用背包问题:

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

创新互联服务项目包括南平网站建设、南平网站制作、南平网页制作以及南平网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,南平网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到南平省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!

例题:

有 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<
潜水员:

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸:一个为氧气,一个为氮气。

每个气缸都有重量和气体容量。

他完成工作所需气缸的总重的最低限度的是多少?

输入格式:

第一行有2个整数 m,n。它们表示氧,氮各自需要的量。

第二行为整数 k 表示气缸的个数。

此后的 k 行,每行包括ai,bi,ci,3个整数。这些各自是:第 i 个气缸里的氧和氮的容量及气缸重量。

输出格式:

仅一行包含一个整数,为潜水员完成工作所需的气缸的重量总和的最低值。

二维费用的01背包问题。f[i][j][k]代表只看前i个气缸,氧气至少为j,氮气至少为k时的大重量(注意氧气和氮气可以多)。

选第i个:

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

不选第i个:

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

本题要求的是最小值, 每个状态为了不被0影响,需要把所有状态更新为INF,特别的,f[0][0][0]=0。

由于是最少需要的氧气和氮气,所以氮气和氧气超出了也是可以的。相当于背包容量不够了也是可以装当前这个物品的。在更新的时候需要额外更新一些状态。比如我们只需要5的氧气,但是当前物品的氧气为8,我们也是可以选择的,f[i][5][j]=f[i-1][0][j]+w。

代码如下:

#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;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章标题:动态规划——二维费用的背包问题-创新互联
标题URL:http://cdxtjz.cn/article/dcihgp.html