Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 1201|回复: 0

[默认分类] 算法设计与分析--01背包问题(动态规划法解决)

[复制链接]
  • TA的每日心情
    开心
    2021-12-13 21:45
  • 签到天数: 15 天

    [LV.4]偶尔看看III

    发表于 2018-7-11 14:05:30 | 显示全部楼层 |阅读模式

    这个学期开的算法设计与分析课程老师说是研究生才要学的课,但是我们大二就要学!
    虽然有难度,但还是要学滴。

    上机课题目有一道0-1背包的问题,上课的时候由于没有听课。。所以只有自己再啃书本了。
    代码虽然不长,但是还是。。很有。。技术含量的。
    本人文笔不是很好,所以就 不多说啦!直接上菜!
    问题描述:
    给定N中物品和一个背包。物品i的重量是W[sub]i[/sub],其价值位V[sub]i[/sub] ,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大??
    在选择物品的时候,对每种物品i只有两种选择,即装入背包或不装入背包。不能讲物品i装入多次,也不能只装入物品的一部分。因此,该问题被称为0-1背包问题。

    问题分析:令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值,则可以得到如下的动态规划函数:
    (1)   V(i,0)=V(0,j)=0
    (2)   V(i,j)=V(i-1,j)  j<w[sub]i  [/sub]
           V(i,j)=max{V(i-1,j) ,V(i-1,j-w[sub]i[/sub])+v[sub]i[/sub]) } j>w[sub]i[/sub]
    (1)式表明:如果第i个物品的重量大于背包的容量,则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的,即物品i不能装入背包;第(2)个式子表明:如果第i个物品的重量小于背包的容量,则会有一下两种情况:(a)如果把第i个物品装入背包,则背包物品的价值等于第i-1个物品装入容量位j-w[sub]i[/sub] 的背包中的价值加上第i个物品的价值v[sub]i;[/sub](b)如果第i个物品没有装入背包,则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然,取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。


      1 #include<stdio.h>


       2
      

       3
      int V[
      200][
      200];
      //
      前i个物品装入容量为j的背包中获得的最大价值
      

       4
      
      int max(
      int a,
      int b)
      

       5 {
      

       6   
      if(a>=b)
      

       7        
      return a;
      

       8   
      else
      return b;
      

       9 }
      

      10
      

      11
      int KnapSack(
      int n,
      int w[],
      int v[],
      int x[],
      int C)
      

      12 {
      

      13     
      int i,j;
      

      14     
      for(i=
      0;i<=n;i++)
      

      15         V[
      0]=
      0;
      

      16     
      for(j=
      0;j<=C;j++)
      

      17         V[
      0][j]=
      0;
      

      18     
      for(i=
      0;i<=n-
      1;i++)
      

      19         
      for(j=
      0;j<=C;j++)
      

      20            
      if(j<w)
      

      21                 V[j]=V[i-
      1][j];
      

      22            
      else
      

      23                 V[j]=max(V[i-
      1][j],V[i-
      1][j-w]+v);
      

      24             j=C;
      

      25            
      for(i=n-
      1;i>=
      0;i--)
      

      26             {
      

      27                 
      if(V[j]>V[i-
      1][j])
      

      28                 {
      

      29                 x=
      1;
      

      30                 j=j-w;
      

      31                 }
      

      32            
      else
      

      33                 x=
      0;
      

      34             }
      

      35             printf(
      "
      选中的物品是:\n
      ");
      

      36            
      for(i=
      0;i<n;i++)
      

      37                 printf(
      "
      %d
      ",x);
      

      38             printf(
      "
      \n
      ");
      

      39         
      return V[n-
      1][C];
      

      40         
      

      41 }
      

      42
      

      43
      void main()
      

      44 {
      

      45     
      int s;
      //
      获得的最大价值
      

      46
          
      int w[
      15];
      //
      物品的重量
      

      47
          
      int v[
      15];
      //
      物品的价值
      

      48
          
      int x[
      15];
      //
      物品的选取状态
      

      49
          
      int n,i;
      

      50     
      int C;
      //
      背包最大容量
      

      51
          n=
      5;
      

      52     printf(
      "
      请输入背包的最大容量:\n
      ");
      

      53     scanf(
      "
      %d
      ",&C);
      

      54     
      

      55     printf(
      "
      输入物品数:\n
      ");
      

      56     scanf(
      "
      %d
      ",&n);
      

      57     printf(
      "
      请分别输入物品的重量:\n
      ");
      

      58     
      for(i=
      0;i<n;i++)
      

      59         scanf(
      "
      %d
      ",&w);
      

      60
      

      61     printf(
      "
      请分别输入物品的价值:\n
      ");
      

      62     
      for(i=
      0;i<n;i++)
      

      63         scanf(
      "
      %d
      ",&v);
      

      64
      

      65     s=KnapSack(n,w,v,x,C);
      

      66
      

      67     printf(
      "
      最大物品价值为:\n
      ");
      

      68     printf(
      "
      %d\n
      ",s);
      

      69   
      

      70     
      

      71 }

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-3-29 03:37 , Processed in 0.310929 second(s), 37 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表