建筑网校排名前十大品牌_网络营销是做什么工作_百度短链接在线生成_成都排名推广

一、DFS暴力深搜（O(2ⁿ)，一般过不了）

• DFS与01背包基本一致（PS：因为质量M也会影响到边界，所以参数应该多一个）

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int M[N],V[N],W[N];
int n,m,v;//当前枚举到第x个位置，剩余体积SPV,剩余质量SPM
int dfs(int x,int SPV,int SPM)
{if(x>n) return 0;if(SPV<V[x] || SPM<M[x])    //容量/质量不够，选不了{return dfs(x+1,SPV,SPM);    //往下一个位置搜索}else if(SPV>=V[x] && SPM>=M[x]){return max(dfs(x+1,SPV,SPM),dfs(x+1,SPV-V[x],SPM-M[x])+W[x]);   //选/不选}   
}void solve()
{cin>>n>>v>>m;   //物品数，最大体积，最大质量for(int i=1;i<=n;i++){cin>>V[i]>>M[i]>>W[i];}int res=dfs(1,v,m);cout<<res<<'\n';}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

二、记忆化搜索（0（N* M* V），一般能过）

• 因为此时DFS函数的参数个数为三个，所以mem数组应该为三维

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int M[N],V[N],W[N];
int n,m,v;
int mem[1007][107][107];//当前枚举到第x个位置，剩余体积SPV,剩余质量SPM
int dfs(int x,int SPV,int SPM)
{if(mem[x][SPV][SPM]) return mem[x][SPV][SPM];int sum=0;if(x>n) sum= 0;else if(SPV<V[x] || SPM<M[x])    //容量/质量不够，选不了{sum= dfs(x+1,SPV,SPM);    //往下一个位置搜索}else if(SPV>=V[x] && SPM>=M[x]){sum= max(dfs(x+1,SPV,SPM),dfs(x+1,SPV-V[x],SPM-M[x])+W[x]);   //选/不选}   mem[x][SPV][SPM]=sum;return mem[x][SPV][SPM];
}void solve()
{cin>>n>>v>>m;   //物品数，最大体积，最大质量for(int i=1;i<=n;i++){cin>>V[i]>>M[i]>>W[i];}int res=dfs(1,v,m);cout<<res<<'\n';}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

三、倒序动态规划

• 只执行归的过程，从边界开始，往起始位置倒推
• PS:此时的状态转移方程与DFS完全一致
• 循环条件与边界参数完全一致

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int M[N],V[N],W[N];
int n,m,v;
int f[1007][107][107];
// int mem[1007][107][107];//当前枚举到第x个位置，剩余体积SPV,剩余质量SPM
// int dfs(int x,int SPV,int SPM)
// {
//     if(mem[x][SPV][SPM]) return mem[x][SPV][SPM];//     int sum=0;//     if(x>n) sum= 0;
//     else if(SPV<V[x] || SPM<M[x])    //容量/质量不够，选不了
//     {
//         sum= dfs(x+1,SPV,SPM);    //往下一个位置搜索
//     }
//     else if(SPV>=V[x] && SPM>=M[x])
//     {
//         sum= max(dfs(x+1,SPV,SPM),dfs(x+1,SPV-V[x],SPM-M[x])+W[x]);   //选/不选
//     }   
//     mem[x][SPV][SPM]=sum;
//     return mem[x][SPV][SPM];
// }void solve()
{cin>>n>>v>>m;   //物品数，最大体积，最大质量for(int i=1;i<=n;i++){cin>>V[i]>>M[i]>>W[i];}for(int i=n;i>=1;i--){for(int j=0;j<=v;j++){for(int k=0;k<=m;k++){if(j<V[i] || k<M[i])  //容量/质量不够，选不了{f[i][j][k]=f[i+1][j][k];}else{f[i][j][k]=max(f[i+1][j][k],f[i+1][j-V[i]][k-M[i]]+W[i]);    //选/不选}}}}cout<<f[1][v][m]<<'\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

四、顺序动态规划

• 相当于从最大数开始递归的过程

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int M[N],V[N],W[N];
int n,m,v;
int f[1007][107][107];
// int mem[1007][107][107];//当前枚举到第x个位置，剩余体积SPV,剩余质量SPM
// int dfs(int x,int SPV,int SPM)
// {
//     if(mem[x][SPV][SPM]) return mem[x][SPV][SPM];//     int sum=0;//     if(x>n) sum= 0;
//     else if(SPV<V[x] || SPM<M[x])    //容量/质量不够，选不了
//     {
//         sum= dfs(x+1,SPV,SPM);    //往下一个位置搜索
//     }
//     else if(SPV>=V[x] && SPM>=M[x])
//     {
//         sum= max(dfs(x+1,SPV,SPM),dfs(x+1,SPV-V[x],SPM-M[x])+W[x]);   //选/不选
//     }   
//     mem[x][SPV][SPM]=sum;
//     return mem[x][SPV][SPM];
// }void solve()
{cin>>n>>v>>m;   //物品数，最大体积，最大质量for(int i=1;i<=n;i++){cin>>V[i]>>M[i]>>W[i];}for(int i=1;i<=n;i++){for(int j=0;j<=v;j++){for(int k=0;k<=m;k++){if(j<V[i] || k<M[i])  //容量/质量不够，选不了{f[i][j][k]=f[i-1][j][k];}else{f[i][j][k]=max(f[i-1][j][k],f[i-1][j-V[i]][k-M[i]]+W[i]);    //选/不选}}}}cout<<f[n][v][m]<<'\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}

五、二维–>一维

• 注意优化的时候需要倒序边界条件，让旧值——>更新旧值
• 可以优化循环条件，省去一个if判断
  for(int j=v;j>=0;j--)—>for(int j=v;j>=V[i];j--)
for(int k=m;k>=0;k--)–> for(int k=m;k>=M[i];k--)

#include <bits/stdc++.h>
using namespace std;const int N = 1007;
int M[N],V[N],W[N];
int n,m,v;
int f[107][107];
// int mem[1007][107][107];//当前枚举到第x个位置，剩余体积SPV,剩余质量SPM
// int dfs(int x,int SPV,int SPM)
// {
//     if(mem[x][SPV][SPM]) return mem[x][SPV][SPM];//     int sum=0;//     if(x>n) sum= 0;
//     else if(SPV<V[x] || SPM<M[x])    //容量/质量不够，选不了
//     {
//         sum= dfs(x+1,SPV,SPM);    //往下一个位置搜索
//     }
//     else if(SPV>=V[x] && SPM>=M[x])
//     {
//         sum= max(dfs(x+1,SPV,SPM),dfs(x+1,SPV-V[x],SPM-M[x])+W[x]);   //选/不选
//     }   
//     mem[x][SPV][SPM]=sum;
//     return mem[x][SPV][SPM];
// }void solve()
{cin>>n>>v>>m;   //物品数，最大体积，最大质量for(int i=1;i<=n;i++){cin>>V[i]>>M[i]>>W[i];}for(int i=1;i<=n;i++){for(int j=v;j>=V[i];j--){for(int k=m;k>=M[i];k--){f[j][k]=max(f[j][k],f[j-V[i]][k-M[i]]+W[i]);    //选/不选}}}cout<<f[v][m]<<'\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ =1; //cin >> _;while (_--) solve();system("pause");return 0;
}