算法进阶之动态规划

电玩女神 2022-06-08 10:49 161阅读 0赞

动态规划的本质，是对问题状态的定义和状态转移方程的定义。  
  
  
     动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。  
  
  
能用动态规划解决的问题的特点

1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子

结构性质。

2) 重叠子问题。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采

取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。  
  
  
01背包问题  
  
  
题目  
  
  
    这题非常有名，只要是计算机专业的应该都有听说过。有N件物品和一个容量为V的背包。第i件物品的体积是

c\[i\]，价值是v\[i\]。求解将哪些物品装入背包可使价值总和最大。

我们把题目具体下， 有5个商品，背包的体积为10，他们的体积为 c\[5\] = \{3,5,2,7,4\};  价值为 v\[5\] =

\{2,4,1,6,5\};  
  
  
问题分析  
  
  
    这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。可以将背包问题的求解看作是进行一

系列的决策过程，即决定哪些物品应该放入背包，哪些不放入背包。  
  
    如果一个问题的最优解包含了物品n，即Xn = 1，那么其余X1, X2, .....,Xn-1 一定构成子问题1,2,.....,n-1

在容量C - cn时的最优解。如果这个最优解不包含物品n,即Xn = 0;那么其余 X1, X2.....Xn-1一定构成了子问题

1,2,....n-1在容量C时的最优解。    
  
  
根据以上分析最优解的结构递归定义问题的最优解    c\[i\]\[w\] = max\{ c\[i-1\]\[w\] , c\[i-1\]\[w- c\[i\]\] + v\[i\]\}  
  
  
解决方案

namespace 动态规划
    {
        public partial class Form1 : Form
        {
            public Form1()
            {
                InitializeComponent();
            }
    
            private void button1_Click(object sender, EventArgs e)
            {
                int i, w;
                int n = 5;   //5个物品
                int  W=17;   //背包载重
                int[] Weights = new int[6] { 0, 3, 4, 7, 8, 9 };  //因为索引都是从0开始的，为了不使得下标越界，所以多定义一个
                int[] Values = new int[6] { 0,4, 5, 10, 11, 13 };
                int[,] c = new int[6, 18];
                for (w = 0; w <= W; w++)
                {
                    c[0,w] = 0;
    
                }
                for (i = 1; i <= n; i++)
                {
                    c[i, 0] = 0;
                    for (w = 1; w <= W; w++)
                    {
                        if (Weights[i] <= w)
                        {  //物品的重量小于背包内的剩余容量
                            if (Values[i] + c[i - 1, w - Weights[i ]] > c[i - 1, w])
                                //物品放进去
                                c[i, w] = Values[i] + c[i - 1, w - Weights[i ]];
                            
                            else//物品不放进去
                             c[i, w] = c[i - 1, w]; 
                        }
                        else  //物品的重量大于背包内的剩余容量
                         c[i, w] = c[i - 1, w]; 
    
                    }
    
                }
                //输出最优值，在背包为最大容量是一定能取得最优值
                textBox1.Text = c[n, W].ToString();
                //求最优解
                int[] x = new int[6];
                for (i = n; i > 1; i--)
                {
                    if (c[i - 1, W] == c[i, W])
                        x[i] = 0;
                    else
                    {
                        x[i] = 1;
                        W = W - Weights[i];
                    }
                }
                if( c[1,W]==0)
                    x[1]=0;
                else
                    x[1]=1;
    
                for (i = 1; i <= n; i++)
                { 
                    if( x[i]==1)
                    {
                        textBox2.Text = textBox2.Text + " " + i.ToString();
                    }
                }
            }
        }
    }