php 网站目录结构,建站推广什么意思,上海自聊自做网站,精密导航问题分析
看到这个问题的同学很容易想到用十层循环暴力计算#xff0c;反正是道填空题#xff0c;一直算总能算得出来的#xff0c;还有些同学可能觉得十层循环太恐怖了#xff0c;写成回溯更简洁一点。像下面这样
#include bits/stdc.h
using namespace std;
in…
问题分析
看到这个问题的同学很容易想到用十层循环暴力计算反正是道填空题一直算总能算得出来的还有些同学可能觉得十层循环太恐怖了写成回溯更简洁一点。像下面这样
#include bits/stdc.h
using namespace std;
int cnt0;
vectorbool used(2023,false);
void dfs(int now,int len,int start) {if(len10){if(now2022){cnt;}return;}for(int istart;i2022-now;i){if(!used[i]){used[i]true;dfs(nowi,len1,i1);used[i]false;}}
}
int main() {dfs(0,0,1);coutcntendl;return 0;
}但是我们分析一下这个时间复杂度大概是 O ( C 2022 10 ) O(C_{2022}^{10}) O(C202210)级别的这个数字太恐怖了要高于 1 0 30 10^{30} 1030的数量级而c代码在平台上运行的速度大概是 1 0 9 10^{9} 109次每秒。所以根本不可能暴力求出答案。而回溯不可以我们可以动态规划嘛。这实际上就是典型的限量背包问题如果不知道什么是限量背包问题可以看我的这篇博客。从物品1~2022中挑选10个物品要求每种物品只能选一次然后装满该背包容量2022有多少种组合将该问题转化为背包问题就很容易解决了。不过要记得用long long这个数字很大
具体代码如下
#includeiostream
using namespace std;
long long int f[11][2023] {0}; //f[j][k]:选择了j个物品满载容积k的背包的组合数
int i, j, k;
int main() {f[0][0]1;for(i1; i2022; i) {//遍历每个物品 for(k2022; ki; k--) {//遍历背包容量从后往前遍历 for(j1; j10; j) {//遍历每个选择数量 f[j][k]f[j-1][k-i];}}}cout f[10][2022];return 0;
}结果
