算法模板-01背包
2021-02-02 13:18
标签：时间复杂度 容量 com 算法 情况 根据 == 一个 模板 01背包：在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2至Wn，与之相对应的价值为P1,P2至Pn。求背包在可以装下的情况下的最大价值是多少？ 1.建立状态：令dp[M][W]为M件物品放入空间为W的背包的最大价值。 2.分析状态转移方程：对每一个物品，仅可以选择放一个进去或者不放，所以对于第i个物品有：将前i个物品放进背包的最大价值为背包里有第i个物品与背包里没有第i个物品中两者的最大价值。 转移方程表达为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-Wi]+Pi);显然 当 i==0 或者 j==0 时：dp[i][j]=0; 3.根据方程编程：时间复杂度( O(M*W) ) 4.代码优化：时间复杂度就不好优化了，但是还可以优化空间的复杂度，dp[i][j] 取决于 dp[i-1][j] 和 dp[i-1][j-w[i]] ,不依赖更前面的数据，所以可以把dp[M][W]压缩为dp[W];但是在编程的时候第二层循环就要倒着来了，因为每次求解我们需要的都是背包容量值不大于j的背包状态。这样还可以略微优化一点第二层循环的时间。时间复杂度（ O(M*(W-w[i)) ） 算法模板-01背包 标签：时间复杂度 容量 com 算法 情况 根据 == 一个 模板 原文地址：https://www.cnblogs.com/xinwang-coding/p/12808045.html
const int maxn=10000;
int W,M,w[maxn],p[maxn],dp[maxn][maxn];
for(int i=1;i){
for(int j=0;j){
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
else dp[i][j]=dp[i-1][j];
}
}
coutdp[M][W];
const int maxn=10000;
int w[maxn],p[maxn],dp[maxn];
for(int i=1;i)
for(int j=W;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+p[i]);
cout
下一篇：汇编语言-基础知识