宁波智能模板建站,企业网站建设公,天河区网站建设,天津做网站找哪家好问题描述#xff1a; 有n种硬币#xff0c;面值分别为V1,V2...,Vn,每种都有无限多。给定非负整数S#xff0c;可以选用多少个硬币#xff0c;使得面值之和恰好为S#xff1f;输出硬币数目的最小值和最大值。0 n 100, 0 S 10000, 1 Vi S。 …问题描述 有n种硬币面值分别为V1,V2...,Vn,每种都有无限多。给定非负整数S可以选用多少个硬币使得面值之和恰好为S输出硬币数目的最小值和最大值。0 n 100, 0 S 10000, 1 Vi S。 分析 本题的本质还是DAG上的路径问题。我们把每种面值看作一个点表示还需要凑足的面值则初始状态为S目标状态为0。若当前的状态i每使用一个硬币j状态便转移到i-Vj。这个模型和嵌套矩形一题类似但也有些明显的不同之处嵌套矩形中并没有确定路径的起点和终点可以把任意矩形放在第一个和最后一个而本题的起点必须是S终点必须是0。把终点固定之后最短路才是有意义的。在嵌套矩形中最短序列显然是空如果不允许空的话就是单个矩形不管怎样都是平凡的而本题的最短路径却不是那么容易确定的。 接下来考虑硬币问题。注意到最长路和最短路的求法是类似的下面只考虑最长路。由于终点固定d(i)的确切含义变为从节点i出发到节点0的最长路径长度。
下面是求最长路的代码错误的 int dp(int S)//错误
{int ansd[S];if(ans0) return ans;ans0;for(int i1;in;i)if(SV[i])ansmax(ans,dp(S-V[i])1);return ans;
}
/*此代码有一个致命的错误即由于节点S不一定真的能到达节点0所以需要用特殊的d[S]值表
示无法到达但在上述代码中如果S根本无法继续往前走返回值是0将被误以为是不能
走已经到达终点的意思。*/ 正确的解法一 int dp(int S)
{int ansd[S];if(ans ! -1) return ans;ans-130;for(int i1;in;i)if(SV[i])ansmax(ans,dp(s-V[i])1);return ans;
}
注意在记忆化搜索中如果用特殊值表示还没有算过则必须将其和其他特殊值(如无解)区分开。 正确的解法二 int dp(int S)
{if(vis[S]) return d[S];vis[S]1;int ansd[S];ans-130;for(int i1;in;i)if(SV[i]){ansmax(ans,dp(S-V[i])1);} return ans;
}尽管多了一个数组但可读性增强了许多再也不用担心特殊值之间的冲突了在任何情况下记忆化搜索的初始化都可以用memset(vis,0,sizeof(vis))执行。 本题要求最小、最大两个值记忆化搜索就必须写两个。在这种情况下还是递推来得更加方便此时需注意递推的顺序
min[0]max[0]0;
for(int i1;in;i)
{min[i]INF; max[i]-INF;
}
for(int i1;in;i)for(int j1;jv;j)if(iV[j]){min[i]min(min[i],min[i-V[j]]1);max[i]max(max[i],max[i-V[j]]1);}
printf(%d %d\n,min[S],max[S]);完整代码 #include stdio.h
#define INF 130
#define maxn 10010
int V[maxn],n;
int min[maxn],max[maxn];inline int Min(int a,int b){return ab?a:b;}
inline int Max(int a,int b){return ab?a:b;}//打印可行的方案
void print_ans(int* d,int S){for(int i1;in;i){if(SV[i] d[S]d[S-V[i]]1){printf(%d ,V[i]);print_ans(d,S-V[i]);break;}}
}int main()
{int S;//输入面值S和面值的种数n while(~scanf(%d%d,S,n)){ for(int i1;in;i){scanf(%d,V[i]);}max[0]0; min[0]0;for(int i1;iS;i){min[i]INF; max[i]-INF;}//递推实现 for(int i1;iS;i){for(int j1;jn;j){if(iV[j]){min[i]Min(min[i],min[i-V[j]]1);max[i]Max(max[i],max[i-V[j]]1);}}}print_ans(min,S); printf( min\n);print_ans(max,S); printf( max\n);printf(min:%d max:%d\n,min[S],max[S]); }return 0;
}
