关于dp(背包)

有关背包,我这几天可是尽受其苦(不得不靠我聪颖的背诵代码的大脑来进行一波操作)

Step 1      01背包

01背包的解释:

01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。如果选择将其放入背包中,由于不清楚之前放入的物品占据了多大的空间,需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

也就是说,每个物品只有一个,只有选或不选的情况

我们只需要利用这一点性质就可以写出下面这套代码

关于01背包的主要代码:

for(int j=;j<=m;j++)
{
for(int i=n;i>=v[j];i--)
{
dp[i]=max(dp[i],dp[i-v[j]]+p[j]);
}
}

Step 2      完全背包

完全背包就是说各个物品有无数多的数量,怎么取都可以(与01背包有及其大的共同点qwq)

就是从低到高排序做。

for(int j=;j<=m;j++)
{
for(int i=v[j];i<=m;i++)
{
dp[i]=max(dp[i],dp[i-v[j]]+p[j]);
}
}

下几篇就是关于一些例题的题解。

上一篇:转:Android文件存储路径getFilesDir()与getExternalFilesDir的区别


下一篇:[Laravel] 10 - WEB API : wrapper