DP总结复习回顾
参考了Peppa_Even_Pig相关文章
什么是DP呢
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。 动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
能采用DP去做的前提一般具有三个性质
1、最优子结构；2、无后效性（不被前面影响）；
背包DP
<1>01背包
有N件物品和一个容量是V的背包，每件物品只能使用一次。 第i件物品的体积是Vi,价值是Wi. 求将哪些物品装入背包，使其总体积不超过背包容量，且总价值最大。输入N，V后，接下来N行，输入Vi,Wi。 问题分析： 01背包本质是由上层状态转移而来（满足条件的前提），由于其只能选一次，状态的转移沿对角线方向；初始化为题目所要求；（一般为f[0][0] = 0; memset(f, 0, sizeof(f));）； 当某一层状态转移满时，其后的状态可能会出现不可预料的错误（一般是由于初始化导致的）（初始化非常重要！！！）（其实最优解就在最后一行的某个地方）；当初始化为0xcf时， 可能会出现f[][]数组中有0xcf+符合条件的最优价值的情况；cout << f[n][m]; 也无法出现最优解；（其实f数组中可能根本没有最优解，（初始化已经出现错误，体现了初始化的重要性），max也没用）； 朴素做法：点击查看代码
#include <iostream>
#include <cstring>
using namespace std;
int f[2005][2005]; //f[i][j]表示前i件物品，容量为j时最大价值；
int m, n;
int w[10005], c[10005];
int main() {
cin >> m >> n;
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
cin >> w[i] >> c[i];
}
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
}
for (int j = w[i]; j <= m; j++) {
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + c[i]);
}
}
cout << f[n][m];
return 0;
}
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int c[10005], w[10005]; //w[i]为第i件物品的重量，c[i]为第i件物品的价值；
int f[10005]; //f[i]为 容量为i时的最大价值；
int m, n; //m为背包容量，n为总物品数量；
int main() {
cin >> m >> n;
memset(f, 0, sizeof(f)); //初始化，等待赋值；
for (int i = 1; i <= n; i++) {
cin >> w[i] >> c[i];
}
f[0] = 0; //初始化，当容量为0时最大价值为0；
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
f[j] = max(f[j], f[j - w[i]] + c[i]);
}
}
cout << f[m];
return 0;
}
点击查看代码
#include<bits/stdc++.h>
#define N 1145
using namespace std;
int v[N],w[N];
int n,V;
int f[N];
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=V;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[V];
return 0;
}
<2>完全背包
也就是将物品改成无限个。 在上面Q&A中已经提及，只需把内层循环顺序即可。点击查看代码
#include<bits/stdc++.h>
#define N 100000
using namespace std;
int m,n;
int f[N],v[N],w[N];
int ans;
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<"max="<<f[m];
return 0;
}
<3>多重背包
也就是一个物品取有限次。 朴素版本：点击查看代码
#include<bits/stdc++.h>
#define N 1010
using namespace std;
int f[N],v[N],w[N],c[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>c[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c[i];j++)
{
for(int k=m;k>=v[i];k--)
{
f[k]=max(f[k],f[k-v[i]]+w[i]);
}
}
}
cout<<f[m];
return 0;
}
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int n, m, num;
int w[1000005], c[1000005]; //要开大一点，因为要分解；
int f[1000005];
int main() {
cin >> n >> m; //物品数量和背包容积；
int a, b, num; //每件物品的重量，价值，个数；
int cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> a >> b >> num;
for (int j = 1; j <= num; j <<= 1) { // j *= 2；
w[++cnt] = a * j;
c[cnt] = b * j;
num -= j; //这样就可以保证每件物品只能选一次（因为如果选多次就超过了原来的num；
}
if (num) { //如果num不能完全分解，那就把剩下的直接存入；
w[++cnt] = a * num;
c[cnt] = b * num;
}
}
for (int i = 1; i <= cnt; i++) {
for (int j = m; j >= w[i]; j--) {
f[j] = max(f[j], f[j - w[i]] + c[i]);
}
}
cout << f[m];
return 0;
}