专栏首页图灵技术域01背包问题动态规划

01背包问题动态规划

首先要明确这张表是至底向上,从左到右生成的。 为了叙述方便,用e2单元格表示e行2列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为2的背包,那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。 对于d2单元格,表示只有物品e,d时,承重为2的背包,所能装入的最大价值,仍然是0,因为物品e,d都不是这个背包能装的。 同理,c2=0,b2=3,a2=6。 对于承重为8的背包,a8=15,是怎么得出的呢? 根据01背包的状态转换方程,需要考察两个值, 一个是f[i-1,j],对于这个例子来说就是b8的值9,另一个是f[i-1,j-Wi]+Pi; 在这里, f[i-1,j]表示我有一个承重为8的背包,当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值 f[i-1,j-Wi]表示我有一个承重为6的背包(等于当前背包承重减去物品a的重量),当只有物品b,c,d,e四件可选时,这个背包能装入的最大价值 f[i-1,j-Wi]就是指单元格b6,值为9,Pi指的是a物品的价值,即6 由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9,所以物品a应该放入承重为8的背包 代码:

C++

#include<stdio.h>
#include<conio.h>
#include<string.h>
int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值,w记录不同物品的重量,v记录不同物品的价值
int max(int x,int y){//返回x,y的最大值
    if(x>y) return x;
    return y;
}
 
int main()
{
    int t,m,i,j;
    memset(f,0,sizeof(f));  //总价值初始化为0
    printf("输入背包承重量t、物品的数目m\n");
    scanf("%d %d",&t,&m);  //输入背包承重量t、物品的数目m
    for(i=1;i<=m;i++)
    {
        printf("%d:",i);
        scanf("%d %d",&w[i],&v[i]);  //输入m组物品的重量w[i]和价值v[i]
    }
    for(i=1;i<=m;i++)//尝试放置每一个物品
    {  
        for(j=t;j>=w[i];j--)
        {
            f[j]=max(f[j-w[i]]+v[i],f[j]);
            
            //在放入第i个物品前后,检验不同j承重量背包的总价值,
            //如果放入第i个物品后比放入前的价值提高了,则修改j承重量背包的价值,否则不变
        }
    }
    printf("%d",f[t]);  //输出承重量为t的背包的总价值
    printf("\n");
    getch();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 01背包问题(动态规划)python实现

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    蛮三刀酱
  • 01背包问题讲解(动态规划)

    假设现在有物品[a,b,c,d,e] 5件,每件物品的价值不同,分别为[1,2,3,4,5],每件物品的重量(KG)也不同,分别为[3,4,1,8,4],现在小...

    虞大大
  • 【动态规划】01背包问题

    前面用动态规划解决了正则表达式的问题,感觉还是不过瘾,总觉得对于动态规划的理解还没有到位,所以趁热打铁,继续研究几个动态规划的经典问题,希望能够借此加深对动态规...

    用户1370629
  • 【动态规划】01背包问题

    前面用动态规划解决了正则表达式的问题,感觉还是不过瘾,总觉得对于动态规划的理解还没有到位,所以趁热打铁,继续研究几个动态规划的经典问题,希望能够借此加深对动态规...

    弗兰克的猫
  • 动态规划法(四)——0/1背包问题

    问题描述 有n个物体,重量分别是w0~wn-1,每个物体放入背包后可获得的收益分别为p0~pn-1,背包载重为M,且所有物体要么放要么不放,不能只放一部分。...

    大闲人柴毛毛
  • 动态规划算法(01背包问题)

    动态规划算法和分治算法类似,也是将待求解问题分成若干个小问题一步步求解,不同的是,每一个小问题求解过程依赖于上一个小问题的解。动态规划问题可以通过填表法来得到解...

    贪挽懒月
  • 动态规划解决01背包问题

    一、问题描述:有n 个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?

    Christal_R
  • 动态规划之三维01背包问题

    动态规划问题是学习算法时一个尤为重要的内容,在讲解什么是动态规划之前,首先来讲一下分而治之。

    不可言诉的深渊
  • 动态规划-背包问题(01背包、完全背包、多重背包)

    背包问题:有多个重量不同、价值不同的物品,以及一个容量有限的背包,选择一些物品装入背包,求最大总价值。 背包问题无法用贪心求最优解,是典型的动态规划...

    唔仄lo咚锵
  • 51NOD 2072 装箱问题 背包问题 01 背包 DP 动态规划

    风骨散人Chiam
  • 【动态规划/背包问题】树形背包问题

    从状态定义我们发现,常规的分组背包问题对物品组的考虑是“线性“的(从前往后考虑每个物品组)。

    宫水三叶的刷题日记
  • 【动态规划/背包问题】多维背包问题

    由于每个字符串只能被选一次,且每个字符串的选与否对应了「价值」和「成本」,求解的问题也是「最大价值」是多少。

    宫水三叶的刷题日记
  • 【动态规划/背包问题】分组背包问题

    但对于「组内」物品而言,由于最多只能选一件物品,因此对于成本相同的多件物品,我们应当只保留价值最大的物品,从而让总的物品数量变少。

    宫水三叶的刷题日记
  • 【动态规划/背包问题】如何将原问题抽象为「01 背包」问题 ...

    在众多背包问题中「01 背包问题」是最为核心的,因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。

    宫水三叶的刷题日记
  • 动态规划算法-背包问题

    温安适
  • 动态规划——背包问题笔记

    给出程序:http://blog.csdn.net/littlethunder/article/details/26575417

    蛮三刀酱
  • 【动态规划】多重背包问题

    这个背包,听起来就很麻烦的样子。别慌,只要你理解了前面的两种背包问题,拿下多重背包简直小菜一碟。

    弗兰克的猫
  • 【动态规划】完全背包问题

    在上一篇中,我们对01背包问题进行了比较深入的研究,这一篇里,我们来聊聊另一个背包问题:完全背包。

    弗兰克的猫
  • 【动态规划/背包问题】树形背包问题练习篇

    今天将练习「树形背包」问题,今天的练习题是一道学习「树形背包/有依赖的背包」问题必做的入门题。

    宫水三叶的刷题日记

扫码关注云+社区

领取腾讯云代金券