记录生活中的点点滴滴

0%

背包问题

动态规划学了一段时间了,dp也做了不少了,但是还是有很多题目就是不会做,可能归根原因就是还是没能一步一步把问题搞透搞懂,所以还是得脚踏实地的练习题目并进行思考,并不是为了刷题而刷题,而是为了搞懂去刷题。今天写一下常见的背包问题,希望以后能做到举一反三,慢慢来吧!

01背包

参考:https://blog.csdn.net/qq_37767455/article/details/99086678

就以这题为例。

首先,这题是一道典型的动态规划题目,肯定是用dp数组去解决,我们先不想什么优化空间,就用最基本的dp去做,对应这题,有number和capacity两个制约条件,要的是价值v最大。

所以,有两维,横坐标是i,代表第i个物品,纵坐标是j,代表空间制约为y。dp【i】【j】就表示当前背包容量为j,前i个物品的最佳组合所对应的价值。

base case是什么呢?dp【0】【..】和dp【..】【0】应该为0,不多解释。

还有,主干其实就是两层for循环,各自从1到终点,然后怎么转移呢?

如果当前i对应的体积,即w【i-1】大于j,那么dp【i】【j】只能等于dp【i-1】【j】;如果小于等于,那么dp【i】【j】还能等于dp【i-1】【j-w【i-1】】+v【i-1】,比较两者的最大值就是dp【i】【j】。

OK,下面我们写代码:

1
2
3
4
5
6
7
8
9
10
11
12
public int maxValue(int n,int cap,int[] w,int[] v){
int[][] dp = new int[n+1][cap+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=cap;j++){
if(w[i-1]>j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
}
}
return dp[n][cap];
}

下图是我们得到的dp表,我们怎样根据它去得到最优解的情况呢?

首先,看dp【i】【j】是否等于dp【i-1】【j】,如果等于,说明第i个不含有,递归dp【i-1】【j】

如果不等于,看dp【i】【j】是否等于dp【i-1】【j-w【i-1】】+v【i-1】,等于说明装了第i个商品,则递归dp【i-1】【j-w【i-1】】

直到i为0结束。

1
2
3
4
5
6
7
8
9
10
int[] isHave = new int[4];//统计是否含有
void find(int i,int j){
if(i==0) return ;
if(dp[i][j]==dp[i-1][j]){
find(i-1,j);//第i个不含有
}else if(j-w[i-1]>=0 && dp[i][j]==dp[i-1][j-w[i-1]]+v[i-1]){
isHave[i-1] = 1;
find(i-1,j-w[i-1]);
}
}

完全背包问题

上面是01背包问题,意思就是我们不能无限使用物品,只能用零次或者一次,还有另外一种背包问题就是完全背包问题,就是物品是无限的。

那么我们思考一下,这种情况下,该这么办?

其实好像差不多,只不过dp【i】【j】的转移方程好像需要换一下了,我们还是先看看上面的:

如果当前i对应的体积,即w【i-1】大于j,那么dp【i】【j】只能等于dp【i-1】【j】;如果小于等于,那么dp【i】【j】还能等于dp【i-1】【j-w【i-1】】+v【i-1】,比较两者的最大值就是dp【i】【j】。

对应完全背包问题,如果w【i-1】大于j,那么dp【i】【j】只能等于dp【i-1】【j】,这个不用变即可;如果小于等于,因为可重复,dp【i】【j】还能等于dp【i】【j-w【i-1】】+v【i-1】,比较两者的最大值就是dp【i】【j】。

1
2
3
4
5
6
7
8
9
10
11
12
public int maxValue(int n,int cap,int[] w,int[] v){
int[][] dp = new int[n+1][cap+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=cap;j++){
if(w[i-1]>j)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-w[i-1]]+v[i-1]);
}
}
return dp[n][cap];
}

背包问题的优化可以参考博客:https://zhuanlan.zhihu.com/p/93857890?utm_source=wechat_session

二维数组是可以优化成一维数组的,但是对于01背包和完全背包,第二层的for循环不一样,重复使用的比如完全背包,从小到大递增即可,但是对于01背包最多只能使用1次的话来说,它需要从大到小往前遍历,否则会影响之前的结果。

这一点我其实还有点迷!