动态规划

1.动态规划

1.1 思路:

先看经典例题01背包

(1)问题描述:

给定 n 件物品,物品的重量为 w[i],物品的价值为 v[i]。现挑选物品放入背包中,假定背包能承受的最大重量为 V,问应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大?

物品编号:1 2 3 4 5

w[i]         :2 3 5 6 8

v[i]         :4 5 8 3 6

 

假设现有背包重量14,如何装才能得到最大价值?

(2)动态规划的思路:

把从0到14的每一个重量能装到的最大价值(最优解)存在一个数组dp[ ]中,这样求dp[8],就可以从前面的dp中找到再相加即可,直到找到14。这样做避免了会找到不是最优解的数。

I 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
dp 0 0 4 5 8 9 12 13 16 17 20 ...      
  0 0 2+2 2+3 2+4 2+5 4+4 4+5 2+8        
                               

经典例题2

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

动态规划

1.2 思路框架

  1. 定义一个存储最优解的dp[]数组。

  2. for循环1:从0到n 求最优解。

  3. for循环2:从0到size()求0到n的每个解。

  4. 更新每个最优解。

  5. 返回dp[amount]。

1.3 代码框架

  //初始化dp数组
   // int* dp = (int*)malloc(sizeof(int)*(amount+1))
   int dp[amount+1];
   for(int i=0;i<amount+1;i++)
     dp[i]=-1;
   dp[0] = 0;
   for(int i=1;i<=amount;i++){
       for(int j=0;j<coins.size();j++){
           //如果当前面值coins[j]比i小,并且i-coins[j]有最优解
           if(coins[j]<i&&dp[i-coins[j]]!=-1){
               //如果dp[i]还未算最优解,或者dp[i]当前最优解比正在算的大,则更新
               if(dp[i]==-1 || dp[i]>dp[i-coins[j]]+1){
                   dp[i] = dp[i-coins[j]]+1;
              }
          }
      }
  }
   return dp[amount];

 

上一篇:LeetCode 322. 零钱兑换 && 动态规划


下一篇:分布式事务消息队列的应用