动态规划解决背包问题

时间：2021-12-06 18:41:04

         动态规划是什么

         动态规划法的思想类似于分治法，基本思路就是把一个问题分解成若干个子问题。求解子问题，然后从子问题中得出原问题的解。因为用分治法解决问题，相同的子问题会被多次求解，所以如果将原来的解保存，就可以减少重复计算。这是我们为什么定义一个二维数组储存我们得到的结果的原因。

         背包问题是什么

         本文我们主要介绍如何用动态规划算法解决0-1背包问题，那么问题来了，背包问题是什么呢？背包问题，是一个经典的问题：

         我们有一个背包，包的容量是w个单位，同时有n个物品供我们选择，第i个物品的重量为w（i）每个物品的价值为v（i），我们在吧物品放入背包的时候，不可以放入半个的物品。求如何让背包中物品的价值最大，这就是背包问题。

          物品可以部分放入背包就是部分背包问题，物品不可以部分放入背包，就是0-1背包问题。

         动态规划法解决背包问题的思路

         针对上面的背包问题，我们解决问题的思路是：在背包中的物品价值最大时，对于第i个物品，有两种可能：1.第i个物品在背包中。2.第i个物品没有在背包中。这就将问题分成了两个子问题：1.背包中有第i个物品，背包的容量为w-w（i） 。背包的价值为在背包容量为w-w（i）时背包所能达到的最大价值。背包中可供选择的物品为n-1（因为在该子问题中i是在背包中的）2.背包中没有第i个物品，那么背包的容量为w。背包中可供选择的物品为n-1（因为在该子问题中i是不在背包中的）。

         这样，无论第i个物品有没有在背包中，我们的可供选择的物品都会减少一个，这时我们的问题就得到了简化。当简化到只有两个物品时，我们就可以很容易的得到子问题的解。然后就可以解决更上一级的子问题的。直到最后得出原问题的解。

         解决问题的具体代码解析

         用动态规划法解决背包问题的代码和解析如下

/* 声明一个背包问题，引入变量n代表物品个数，W代表背包的空间，weights是一个指针，指向了当前的背包剩余空间，values代表了背包中物品的价值*/
     int i ,w;/*声明变量，i表示第i个物品，w表示假设的背包空间*/
     int ** c = (int ** )malloc(sizeof (int * ) * (n+ 1<span style="font-family: Arial, Helvetica, sans-serif;">))</span>
     /*Int **c 代表定义了一个双重指针，双重指针的意思就是指向指针的指针。
malloc（） 是一个函数，功能是申请一个空间，大小为括号中的值。

（int ** ）代表强制转化，因为malloc函数的返回值是void* 类型，，如果写成：int**c= malloc (sizeof(int*)*（n+1）); 则程序无法通过编译，报错：“不能将 void* 赋值给 int * *类型变量”。所以必须通过 (int **) 来将强制转换。


sizeof(int*)*（n+1） 表示了一个空间的大小，表示开辟了一个大小为sizeof(int*)*（n+1）的空间。其中的sizeof（int * ） 代表我们定义的空间的一个单位的大小是一个指针所占用的空间的大小。而* （n+1）表示的是，我们总共定义了n+ 1 个这样的单位。因为一个单位可以存放一个指针，所以我们可以存放n+1个指针。*/
     for （i = 0；i<=n ;i++）/*遍历刚申请的空间*/
          c[i]= (int n *)malloc (sizeof (int )* (w+1));
         /*C[i] 双重指针中第i个指针指向的指针位置


        （Int*）强制转换，类似于（int**）
         sizeof（int）*（ w+1） 定义一个空间，空间中每个单位的大小为int类型的大小，总共有w+ 1个这样的单位。


        这就表示我们定义了（n+1）x（w+1）个单位的int类型的空间。可以用于存放大小为n行w列的一个二维数组。*/
/* 初始化二维数组*/
     for (w=0;w<=W;w++)
          c[0][w]=0;/*可选择物品为0的时候，背包中的可放入的物品价值为0*/
     for（i=1;i<=n;i++）{ /*用循环的方式，将原来的问题拆分成小问题*/
          c[i][0]=0;/*在背包的空间为0的时候，背包中的可放入的物品价值为0*/
          <pre name="code" class="plain" style="font-size: 18px;">          /* 循环得到w从1到W的情况下的最优解*/<span style="font-family: Arial, Helvetica, sans-serif;"> </span>
<pre name="code" class="plain" style="font-size: 18px;">          for (w=1;w<=W ;w++){
          if（weights[i-1]<=w）/*如果背包剩余空间大于物品所需空间*/
               if（values[i-1]+ c[i-1][w-Weights[i-1]]>c[i-1][w])/*如果放入物品时的价值大于不放入*/
               {
                c[i][w]=values[i-1]+c[i-1][w- Weights[i-1]]/*将物品放入背包*/
               }
               else{
               c[i][w]=c[i-1][w];/*物品不放入背包*/
               }
           <pre name="code" class="plain" style="font-size: 18px;">          else<pre name="code" class="plain">              c[i][w]=c[i-1][w];
           }

<pre name="code" class="plain">      }
      return c;
}

</pre><pre>
 
  


 
 


 

 
 
         
 
 


标签：
相关文章