当前位置:网站首页>关于01背包个人的一些理解

关于01背包个人的一些理解

2022-07-06 22:13:00 晴天依旧天晴

01背包

01背包题目

思路剖析

1.当我们第一次看到题目的时候,很容易想到运用贪心的思想,每次拿性价比最大的物品。

容易举出反例:

3 7
6 10 //1.666...
5 8 // 1.6
2 3 //1.5

2.接着我们很自然的就可以想到,既然运用贪心的思想不行,那么就枚举所有选取物品的情况,也就是组合。

于是我们就可以定义状态

\(dfs(i,v,ans)\) 表示我搜索到了第 \(i\) 个物品,此时已经选的物品的总体积为 \(v\) , 所得到的价值为 \(ans\)

当我们将 \(N\) 个物品全都搜完后,若 \(v \le M\) ,则更新我们的答案。

在这个过程中,我们可以发现 , 对于一个状态 \(i,v,ans\) ,它可以从 \(i-1,v,ans\)\(i-1,v-v_i,(ans-w_i)+w_i\) 转移过来(分别对应了我选不选第 \(i\) 个物品的情况),但由于他所剩的物品个数一样,已经选的体积一样,所以尽管从两个不同的状态转移过来,所得的价值不同,但是之后能够遍历到的情况都是相同的。

显然有所得价值更大的状态,得到的结果优于价值更小的状态

这就是最优子结构性质,正因为这个过程具有最优子结构性质,我们在进行下一阶段计算的时候,就免去了绝对不可能是最优的答案的多余的计算,所以我们可以通过他将搜索转化为DP,当然,这过程中同时具无后效性原则重叠子问题

简单解释一下重叠子问题优化的部分。当我已经知道状态 \(dp_{i,v}\) 所能获得的最大价值时,我将它记录下来,之后再遍历到这个状态,我直接就能返回我的最优解了,而不用继续搜下去,重新求解。这就要求了我们DP的问题具有该性质,否则就等同于没有记录,也就没有优化一说了。

无后效性则保证了我求出来的最优解不会被后面所影响,一定是最优的。

3.简单总结一下

状态: \(dp_{i,j}\) 表示以在前 \(i\) 个物品中,选取体积为 \(j\) 的物品,得到的最大价值。

状态转移方程:

\(dp[i][j] = \max(dp[i-1][j],dp[i-1][j-v_i]+w_i)\)

code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,v[3500],w[3500],dp[12885];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
	memset(dp,0xcf,sizeof(dp));//赋值为-INF,表示该状态不可达,这里要特别注意,不能赋值为0,如果赋值为0的话,则表示容积为j的背包所能获得的最大价值,与我们所定义的状态相悖。
	dp[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=v[i];j--){
			dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++) ans=max(ans,dp[i]);//找到最佳答案。
	cout<<ans<<endl;
	return 0;
}

唔,当然,如若是01背包的话,用 \(dp_{i,j}\) 表示前 \(i\) 个物品中,用容积为 \(j\) 的背包所能获得的最大价值也是ok的,但如果题目要我们恰好要把容积为 \(M\) 的背包装满,这个状态所得到的答案就不一定正确了

我给出的代码是已经优化过的版本,具体过程相信很多大佬都比我讲得好,这里主要分享我的一个思路,希望可以帮助自己巩固复习,也可以帮到大家理解。

$ \text{-END-}$

\(2022.7.6\)

原网站

版权声明
本文为[晴天依旧天晴]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/lzyan-blog/p/16452724.html