爱站网关键词密度,wordpress 能用的水印,软件工程可以做什么工作,5g云网站建设【题目链接#xff1a;NYOJ-325】 一道以我名字命名的题目#xff0c;难道要我生日的时候再A#xff1f; 思路#xff1a;依旧深搜#xff0c;但这个问题应该有一个专有名词吧#xff0c;看别的博客说是 “容量为 sum/2 的背包问题”#xff0c;不懂。。。 1 // abs() …【题目链接NYOJ-325】 一道以我名字命名的题目难道要我生日的时候再A 思路依旧深搜但这个问题应该有一个专有名词吧看别的博客说是 “容量为 sum/2 的背包问题”不懂。。。 1 // abs() 对应头文件 stdlib.h 返回int参数 2 // fabs() 对应头文件 math.h 返回double参数 3 #includecstdio4 #includecstring5 #includestdlib.h 6 int W[22],sum,m,n;7 void dfs(int cur,int total){8 int t abs(sum - total * 2);9 if(t m)
10 m t;
11 if(cur n){
12 // int t abs(sum - total * 2);
13 // if(t m)
14 // m t;
15 return;//递归边界
16 }
17 if(total sum / 2){ //剪枝
18 // int t abs(sum - total * 2);
19 // if(t m)
20 // m t;
21 return;
22 }
23 dfs(cur 1,total W[cur]); //结点分支。加右分支
24 dfs(cur 1,total); //节点分支。不加左分支
25 }
26 int main(){
27 while(~scanf(%d,n)){
28 memset(W,0,sizeof(W));
29 sum 0;
30 m 10001;
31 for(int i 0;i n;i){
32 scanf(%d,W[i]);
33 sum W[i];
34 }
35 dfs(0,0);
36 printf(%d\n,m);
37 }
38 return 0;
39 } 渐渐对搜索有了一些认识刚开始完全无头绪要多练习加油 最优解 也就是动脑筋剪枝。 1 #includecstdio2 #includecstring3 #includealgorithm4 using namespace std;5 6 int a[25];7 int s[25];8 int n;9 int V;
10 int ans;
11
12 void DFS(int i,int v)
13 {
14 if(in1)
15 {
16 ansmax(ans,v);
17 return;
18 }
19 //如果背包已经装满则不再考虑其他情况。
20 //如果背包中已有物品加上现有可选物品的总重量都不大于已知的最优解则剪枝
21 if(ansV||vs[n]-s[i-1]ans)
22 return;
23 if(a[i]vV)
24 {
25 DFS(i1,va[i]);
26 }
27 DFS(i1,v);
28 }
29
30 int main()
31 {
32 while(scanf(%d,n)1)
33 {
34 s[0]0;
35 for(int i1;in;i)
36 {
37 scanf(%d,a[i]);
38 s[i]s[i-1]a[i];
39 }
40 Vs[n]/2;
41 ans0;
42 DFS(1,0);
43 anss[n]-ans-ans;
44 printf(%d\n,ans);
45 }
46 return 0;
47 } 转载于:https://www.cnblogs.com/zhengbin/p/4486572.html
