Loading...
墨滴

程序小猿

2021/03/29  阅读:30  主题:蔷薇紫

0-1背包问题怎么解?

对于背包问题,相比有很多读者一见到就头疼。不知道什么时候用一维数组什么时候用二维数组,不知道什么时候正向遍历什么时候反向遍历,不知道数组中存什么东西。。。。。。

今天我们总结了背包问题的常见解法,并辅以例题与大家讲解。解背包问题的常见步骤一般如下:

  1. 根据函数返回值确定dp数组的类型。如果函数返回int,那么dp数组存int;如果函数返回boolean,那么dp数组存boolean

  2. 确定dp数组的最后一个值就是要返回的值

  3. 查看题目中变量数目,确定dp数组的维度,变量数即为维度数

  4. 写出状态转移方程

  5. 写出函数整体框架,包括: new一个dp数组并将其大小设为比原始大1,将状态转移方程翻译成for循环,函数最终返回dp数组的最后一个值

  6. 处理边界值和条件

  7. 观察状态转移方程,可画表格查看状态转移方程的依赖,删减维度,优化算法

完全背包

例题1:322零钱兑换(中等)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 你可以认为每种硬币的数量是无限的。

题目很简单,我们按照文章开头的思路走一遍。首先据函数返回值确定dp数组的类型int。然后确定dp数组存储的就是最少的硬币个数。第三步确定dp数组的维度,题目中有两个变量,硬币的数量和总金额,所以dp数组是2维的。

然后就开始我们的编码,首先new一个二维的dp数组int[][] dp = new int[coins.length+1][amount+1]。写下我们的基本框架:

public int coinChange(int[] coins, int amount) {
    int[][] dp = new int[coins.length+1][amount+1];

    for(int i=0;i<coins.length;i++){
        for(int j=0;j<amount;j++){
          dp[i][j] = ;
        }
    }

    return dp[coins.length][amount];
}

然后确定状态转移方程。第i个硬币凑成j所需最小的硬币个数为不需要当前硬币——第i个硬币凑成j所需最小的硬币个数,或者需要当前硬币——第i个硬币凑成j-coins[i]最小的硬币个数+1(因为硬币数量无限)

翻译成代码的形式,dp[i][j] = Math.min(dp[i][j],dp[i][j-coins[i-1]]+1)

编写代码,考虑jcoins[i-1]的大小关系:

  public int coinChange(int[] coins, int amount) {
      int[][] dp = new int[coins.length+1][amount+1];

      for(int i=1;i<coins.length;i++){
          for(int j=0;j<amount;j++){
              dp[i][j] = dp[i-1][j];
              if(j>=coins[i-1])
                  dp[i][j] = Math.min(dp[i][j-coins[i-1]], dp[i-1][j]);
          }
      }

      return dp[coins.length][amount];
  }

最后处理初始化条件,搞定代码:

public int coinChange(int[] coins, int amount) {
    int[][] dp = new int[coins.length+1][amount+1];
    for(int i=0; i<=coins.length; i++){
        for(int j=0;j<=amount;j++)
            dp[i][j] = amount+1;
        dp[i][0] = 0;
    }

    for(int i=1;i<=coins.length;i++){
        for(int j=0;j<=amount;j++){
            dp[i][j] = dp[i-1][j];
            if(j>=coins[i-1])
                dp[i][j] = Math.min(dp[i][j-coins[i-1]]+1, dp[i][j]);
        }
    }

    return dp[coins.length][amount]==amount+1?-1:dp[coins.length][amount];
}

观察代码,我们发现dp[i][*]只与dp[i-1][*]dp[i][*]有关,即只与它前一个状态有关,所以完全可以删除这一个维度,修改代码如下:

  public int coinChange(int[] coins, int amount) {
      int[] dp = new int[amount+1];

      for(int j=0;j<=amount;j++)
          dp[j] = amount+1;
      dp[0] = 0;

      for(int i=1;i<=coins.length;i++){
          for(int j=0;j<=amount;j++){
              if(j>=coins[i-1])
                  dp[j] = Math.min(dp[j-coins[i-1]]+1, dp[j]);
          }
      }

      return dp[amount]==amount+1?-1:dp[amount];
  }

你们学会了吗?那来动手做一下下面这题吧!

例题2:518零钱兑换II(中等)

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

第一步写好整体框架:

public int change(int amount, int[] coins) {
    int[][] dp = new int[coins.length+1][amount+1];

    for(int i=1;i<=coins.length;i++){
      for(int j=0;j<=amount;j++){
          dp[i][j] = 
      }
    }

    return dp[coins.length][amount];
}

第二步确定状态转移方程,第i个硬币凑成j的组合数为不需要当前硬币——第i个硬币凑成j的组合数+需要当前硬币——第i个硬币凑成j-coins[i]的组合数(因为硬币数量无限)

翻译成代码的形式,dp[i][j] = dp[i][j] + dp[i][j-coins[i-1]]

编写代码,考虑jcoins[i-1]的大小关系:

public int change(int amount, int[] coins) {
    int[][] dp = new int[coins.length+1][amount+1];

    for(int i=1;i<=coins.length;i++){
      for(int j=0;j<=amount;j++){
          dp[i][j] = dp[i-1][j];
          if(j>=coins[i-1]):
            dp[i][j] = dp[i][j] + dp[i][j-coins[i-1]];
      }
    }

    return dp[coins.length][amount];
}

最后处理初始化条件,搞定代码:

public int change(int amount, int[] coins) {
    int[][] dp = new int[coins.length+1][amount+1];
    for(int i=0; i<=coins.length; i++)
        dp[i][0] = 1;

    for(int i=1;i<=coins.length;i++){
      for(int j=0;j<=amount;j++){
          dp[i][j] = dp[i-1][j];
          if(j>=coins[i-1])
            dp[i][j] = dp[i][j] + dp[i][j-coins[i-1]];
      }
    }

    return dp[coins.length][amount];
}

观察代码,删除维度,修改代码如下:

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];

        dp[0] = 1;

        for(int i=1;i<=coins.length;i++){
          for(int j=0;j<=amount;j++){
              if(j>=coins[i-1])
                dp[j] = dp[j] + dp[j-coins[i-1]];
          }
        }

        return dp[amount];
    }
}

你学会了吗?学会了点一个“在看”吧!下期讲0-1背包问题!

程序小猿

2021/03/29  阅读:30  主题:蔷薇紫

作者介绍

程序小猿