背包问题常见题型

80 阅读 0 评论 53 点赞

我是靠谱客的博主多情画板，最近开发中收集的这篇文章主要介绍背包问题常见题型，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

背包问题`oj`汇总

前段时间试了一个几个互联网公司的笔试题，发现几个问题用的递归都没有能够达到 100% 的AC，于是准备重新温习一下递归和动态规划方面的内容。

而背包问题无疑是一个很好的补充：这里会陆续加入在oj中我认为的背包问题

http://www.lintcode.com/zh-cn/problem/backpack-ii/

给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？

这大概是基础的背包问题，注意到第二层循环假设的是如果去掉这么多容量换装这个物品怎么样

public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int[] V) {
// write your code here
int[] dp = new int[m + 1];
for (int i = 0; i < A.length; i ++){
for (int j = m; j >= A[i]; j --){
dp[j] = Math.max(dp[j],dp[j-A[i]]+V[i]);
}
}
return dp[m];
}
}

http://www.lintcode.com/zh-cn/problem/backpack/

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

直接动态 dp 即可：


public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
// write your code here
int []dp = new int[m+1];
for (int i = 0; i < A.length; i ++){
for (int j = m; j >= A[i]; j --)
dp[j] = Math.max(dp[j],dp[j-A[i]]+A[i]);
}
return dp[m];
}
}

http://www.lintcode.com/zh-cn/problem/johns-backyard-garden/

约翰想在他家后面的空地上建一个后花园，现在有两种砖，一种3 dm的高度，7 dm的高度。约翰想围成x dm的墙。如果约翰能做到，输出YES，否则输出NO。

我觉得没有设置背包的大小，不知道怎么使用动态规划解决

一个简单的递归：

public class Solution {
/**
* @param x: the wall's height
* @return: YES or NO
*/
public String isBuild(int x) {
// write you code here
boolean ans = findWays(x);
if (ans)
return "YES";
else
return "NO";
}
public boolean findWays(int x){
if(x < 0)
return false;
else if(x == 0)
return true;
else
return findWays(x - 3) || findWays(x - 7);
}
}

http://www.lintcode.com/zh-cn/problem/cutting-a-rod/

给一个 n 英寸长的杆子和一个包含所有小于 n 的尺寸的价格. 确定通过切割杆并销售碎片可获得的最大值.例如，如果棒的长度为8，并且不同长度部件的值如下，则最大可获得值为 22(通过切割两段长度 2 和 6 )

先试一下动态规划的方法：

再加入一层循环，将一个多选择问题重新转化为单选择的问题（比如 4，这里因为加入了一层循环可以将备选的段落改为 1 1 1 1 2 2 3 4）（时间为2170 ms）

下一个模型中做出了优化（取消了循环）：

public class Solution {
/**
* @param prices: the prices
* @param n: the length of rod
* @return: the max value
*/
public int cutting(int[] prices, int n) {
// Write your code here
int []helpArray = new int[n + 1];
helpArray[0] = 0;
for (int i = 0; i < prices.length; i ++){
for (int k = 0; k < n /( i + 1); k ++){
for (int j = n; j > i; j --){
helpArray[j] = Math.max(helpArray[j],helpArray[j-i-1]+prices[i]);
}
}
}
return helpArray[n];
}
}

这个地方再使用递归的话就可能出现因为数目过大导致无法递归的次数过多了，这里试一下：在 49% 的时候超时了

public class Solution {
/**
* @param prices: the prices
* @param n: the length of rod
* @return: the max value
*/
public int cutting(int[] prices, int n) {
// Write your code here
int sum = 0;
sum = findWays(0,prices,n,0);
return sum;
}
public int findWays(int index,int[] prices, int n,int sum){
if (n < 0)
return 0;
if (n == 0)
return sum;
if (index < prices.length - 1)
return Math.max(Math.max(findWays(index,prices,n-index-1,sum + prices[index]), findWays(index+1,prices,n-index-1,sum + prices[index])),findWays(index+1,prices,n,sum));
return findWays(index,prices,n-index-1,sum + prices[index]);
}
}

http://www.lintcode.com/zh-cn/problem/coin-change/

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1.

先用递归的思路（在22%内存错误了）：

public class Solution {
/**
* @param coins: a list of integer
* @param amount: a total amount of money amount
* @return: the fewest number of coins that you need to make up
*/
public int coinChange(int[] coins, int amount) {
// write your code here
return findWays(coins,amount,0,0);
}
public int findWays(int[] coins, int amount,int sum,int index){
if (amount == 0)
return sum;
if (amount < 0)
return Integer.MAX_VALUE;
if (index < coins.length - 1){
return Math.min(Math.min(findWays(coins,amount - coins[index],sum + 1,index), findWays(coins,amount - coins[index],sum + 1,index + 1)),findWays(coins,amount,sum,index+1));
}
return findWays(coins,amount - coins[index],sum + 1,index);
}
}

于是换用一次正常动态规划的思路（运行时间较短）：

这个思路刚开始陷入了误区，这个时候就要注意：为什么多次重复第二层循环的 j 是从低到高，而仅一次重复的则是从高到低。可以看到从低到高可以去修改之前修改过的元素，而从高到低则不能修改。

public class Solution {
/**
* @param coins: a list of integer
* @param amount: a total amount of money amount
* @return: the fewest number of coins that you need to make up
*/
public int coinChange(int[] coins, int amount) {
// write your code here
int[] dp = new int[amount + 1];
for(int i = 0; i < amount + 1;i ++)
dp[i] = 10000000;
dp[0] = 0;
for (int i = 0; i < coins.length; i++){
for (int j = coins[i]; j <= amount; j ++){
dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
}
}
return dp[amount] == 10000000 ? -1 : dp[amount];
}
}

在这个思路上，对上面 杆子分割 的动态规划做一个优化：

public class Solution {
/**
* @param prices: the prices
* @param n: the length of rod
* @return: the max value
*/
public int cutting(int[] prices, int n) {
// Write your code here
int []helpArray = new int[n + 1];
helpArray[0] = 0;
for (int i = 0; i < prices.length; i ++){
for (int j = i + 1; j <= n; j ++){
helpArray[j] = Math.max(helpArray[j],helpArray[j-i-1]+prices[i]);
}
}
return helpArray[n];
}
}