算法—动态规划简述

动态规划，动态规划主要是用于求最值的问题，我认为比较重要的东西是 3部分：
1.找到迭代式，也是状态转换方程（注意不是递归，不过递归也是可以做的，但是却不能体现动态规划的好处-“可以通过前面的值来推导出当前的值”，其实这也有个问题，就是必须保证前面的值是无后效性，就是必须保持独立性）
2.设置初始值 （一般考虑 0、1 、2等几个简单的状态）
3.写出代码

下面我列举了两个动态规划的思想 1.0/1背包问题 2.硬币问题

一：0/1背包问题
0/1 背包问题，主要是通过一个限定的 承载量来获得价值最多的物品。其实也是可以用 贪婪算法来做的，但是现在我们就讨论一下动态规划
1.状态方程
（1）首先对 n个物体编号 为： 0、1、2、3... n-1 ;
(2) 对于这个问题 我们首先要知道 两个变量 就是 物件的个数和总容量，因为不管怎么样我们不能超过总的容量
（3）C[i][j] ：表示前i（包括i）个物体，在总容量为j的， 价值最多的
(4) 方程 C[i][j] = max{C[i-1][j],C[i-1][j-W[i]] + P[i]}，
对与 前i个物件，我们可以这样考虑，对于第 i个物件 我们可以放入（保证容量是够的 而且 比前i-1个物件在j容量的价值要大 ），也可以不放入（容量不够，或者 比前i-1个物件在j容量的价值要小），反正就是在容量的允许下，取最大值

/* 
 * 背包问题
 *
 **/

void bagOf0_1() {
    
    
    //背包问题
    int W[] = {0,3,4,5};//重量
    int P[] = {0,4,5,6};//价值
    
    int C[4][11] = {0};
    //C[i][j] = max{C[i-1][j],C[i-1][j-W[i]] + P[i]}
    //C[i][j] 表示前i个物件 在容量为j 的总价值
    for (int i = 1; i < 4; i++) { //宝石的编号
        
        for (int j = 1 ; j < 11; j++) { //剩余容量的编号
            
            int value1 = C[i-1][j];
            int value2 = j-W[i]>=0?(C[i-1][j-W[i]]+P[i]):value1;
            
            C[i][j] = MAX(value1, value2);
        }
        
    }
    
    for (int i = 1; i < 4; i++) { //宝石的编号
        
        printf("\n");
        for (int j = 1 ; j < 11; j++) { //剩余容量的编号
            
            printf(" %2d ",C[i][j]);
        }
        
    }
    
    /*递归调用**/
    NSLog(@" maxValue = %d",bagOf0_3(4,10,P,W));
}

下面介绍一个递归调用的方法

/* 递归实现 01背包问题 **/
int bagOf0_3(int i,int j,int P[],int W[]) {
    
    if (i == 0 || j == 0) {
        
        return 0;
    }
    
    if (j-W[i] >= 0) {
        return MAX(bagOf0_3(i-1,j,P,W), bagOf0_3(i-1,j-W[i],P,W)+ P[i]);
    }else {
        return bagOf0_3(i-1,j,P,W);
    }
    
    
}

二：硬币问题问题
描述： 有硬币是 1元 3元 5元，就设x 需要最少多少个硬币数量

/*
 * 递推式 是 dp[i] = min{dp[i - iconType[0]] + 1, dp[i - iconType[1]] + 1,..., dp[i - iconType[j]] +1,...}
 **/
void needMoneyCount_2() {
    
    //假设100 元需要几个硬币
    int dp[101] = {0};
    int iconType[] = {1,3,5};
    int iconTypeCount = sizeof(iconType)/sizeof(int);
    int dpCount  = sizeof(dp)/sizeof(int);
    //1.设置初始值
    // dp[i] = k, 表示i元钱，需要多少个硬币
    dp[0] = 0;
    //2.写出迭代式 dp[i] = min{dp[i - iconType[0]] + 1, dp[i - iconType[1]] + 1,..., dp[i - iconType[j]] +1,...}
    //3.从下标为1 开始计算 （这里有个缺点就是 必须保证 每个值都有解，否则往下走，就不能根据前面计算好的值来）
    for (int i = 1;i < dpCount;i++) {
        
        int minCount = INT_MAX;
        
        for (int j = 0; j < iconTypeCount; j ++) {
            
            if (i - iconType[j] >=0) {
                
                if (minCount > (dp[i - iconType[j]] +1)) {
                    minCount = dp[i - iconType[j]] +1;
                }
                
            }
        }
        
        dp[i] = minCount;
        
    }
    
    printf("硬币的动态规划 \n");
    for (int i = 1 ; i < dpCount; i++) {
        
        printf("dp[%d] = %d、 ",i,dp[i]);
        
    }
    
    
    
}