目录
- 背包问题
- 01背包问题
- 完全背包
- 多重背包问题 I
- 多重背包问题 II
- 分组背包
- 线性DP
- 最长上升子序列
- 最长上升子序列 II
- 最长公共子序列
- 最短编辑距离
- 编辑距离
- 区间DP
- 石子合并
背包问题
01背包问题
状态表示 :
f
[
i
]
[
j
]
f[i][j]
f[i][j] 前
i
i
i个物品中,体积为
j
j
j的最大价值
状态转移 :
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
(
j
−
v
<
0
)
f[i][j] =f[i-1][j](j-v>w[i]>>s[i];
for(int i=1;i=0;j--)
{
for(int k=1;km;
for(int i = 1;i>v>>w>>s;
for(int k = 1;k= k*v;j--)
f[j] = max(f[j],f[j-k*v]+k*w);
s-=k;
}
if(s)
{
for(int j = m ;j>=s*v;j--)
{
f[j] = max(f[j],f[j-s*v]+s*w);
}
}
}
coutm;
for(int i=0;i>s[i];
for(int j=0;j>v[i][j]>>w[i][j];
}
}
for(int i=0;i=0;j--){
for(int k=0;k=1;k--)也可以
if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
cout
