202003 pmn的变形使用讲课

admin

1、复习标准的pmn
2、体会相邻的数字差小于4 和 间隔排列
3、任意个的组合的两种写法
4、数字分解，1*2的骨牌覆盖，装箱问题的理解。
5、加一个参数的简洁写法。
6、布尔数组的用法（8皇后问题）。
7、深度不确定的搜索（因数分解）。

admin

8皇后问题：8*8的国际象棋棋盘，摆8个皇后，相互不攻击，皇后攻击同一行，同一列，正反两斜对角线的子。
搜索，总共8个皇后，每个皇后8个位置可能，满足条件就行，和8选8有相似之处：
void  dfs(int i)
{  
    if(i>9)  pr();
    else for (int k=1;k<=8;k++)
      if (can(i,k))  第i行可以放在第k个位置
       {
            a(i)=k;dfs(i+1);
        }
}
那么重点就在写函数can(i,k) 上
暴力搜索
bool  can(int i,int k)
{  
     bool b=1;
     for (int j=1;j<=i-1;j++)  if a(j)==k  b=0;   前面i-1 行某个和我同列
     for (int j=1;j<=i-1;j++)  if j+a(j)==k+i  b=0;    前面i-1 行某个和我同对角线
     for (int j=1;j<=i-1;j++)  if ???  b=0;   前面i-1 行某个和我同反对角线
  returnb;
}

admin

棋盘怎么表示，我建议大家用a(0)-a(15)表示16个格子，当然也人想用a(1)(1)到 a(4)(4)，等下你就会发现a(0)-a(15)好！

admin

第二种，枚举每个数组，两种情况，选和不选

1. /// 5个选任意个
   
2. #include <iostream>
   
3. using namespace std;
   
4. const int mm=10;
   
5. bool b[mm];  ///布尔数组 表示这个人是否被选
   
6. int n=5;
   
7. void pr()   ///输出时候枚举是否被选
   
8. { for (int i=1;i<=n;i++) if(b[i]==1) cout<<i;cout<<endl; }
   
9. void dfs(int i)
   
10. {
    
11.         if(i>n) pr();
    
12.         else  
    
13.         for (int k=0;k<=1;k++)  ///枚举选和不选两种情况 0 -不选 1 选
    
14.         {b[i]=k;dfs(i+1);}
    
15. }
    
16. int main()
    
17. {        dfs(1);return 0;}

复制代码

admin

1049装箱问题： 本质就是选出任意个数字，加起来的总和<=V 又最近接V，那我枚举所有的可能求出所有的总和，看看谁最接近V就是了。套用第二种组合的做法：仅仅改动了输出部分，加上了求和和判断。

1. /// 5个选任意个
   
2. #include <iostream>
   
3. using namespace std;
   
4. const int mm=33;/// 最多
   
5. bool b[mm];  ///布尔数组 表示这个人是否被选
   
6. int V,n,sum,a[mm],ans;
   
7. void pr()   
   
8. {
   
9.         sum=0;
   
10.         for (int i=1; i<=n; i++) if(b[i]==1) sum+=a[i];
    
11.         if (sum<=V)
    
12.          ans=min(ans,V-sum);/// 求最小值
    
13. }
    
14. void dfs(int i)
    
15. {
    
16.         if(i>n) pr();
    
17.         else
    
18.                 for (int k=0; k<=1; k++) ///枚举选和不选两种情况 0 -不选 1 选
    
19.                 {
    
20.                         b[i]=k;
    
21.                         dfs(i+1);
    
22.                 }
    
23. }
    
24. int main()
    
25. {
    
26.         cin>>V>>n;ans=999999;
    
27.         for (int i=1;i<=n;i++) cin>>a[i];
    
28.         dfs(1);
    
29.         cout<<ans;
    
30.         return 0;
    
31. }

复制代码

但是这样做超时了一些解，因为效率不高，哪些地方可以改进呢？

admin

重要讲讲第三个知识点：任意个组合的两种写法：
第一种dfs(int i) 和前面一样，枚举第i个位置选哪个数字。
第二种dfs(int i) 新思路：第i个数字是否被选中。
体会：第一种 按位置选人，第二种，按人选

admin

第一种，和前面的一样，但是去掉递归程序里面的if (i>n) ，因为每个都要输出，不是到n个才输出

1. /// 5个选任意个
   
2. #include <iostream>
   
3. using namespace std;
   
4. const int mm=10;
   
5. int a[mm],n=5;
   
6. void pr(int x)
   
7. { for (int i=1;i<=x;i++)  cout<<a[i];cout<<endl; }
   
8. void dfs(int i)
   
9. {
   
10.         pr(i-1);
    
11.         for (int k=a[i-1]+1;k<=n;k++)
    
12.         {a[i]=k;dfs(i+1);}
    
13. }
    
14. int main()
    
15. {        a[0]=0;        dfs(1);return 0;}

复制代码

admin

两种思路有相似，也有不同，好好体会。一般情况下，第2中用的多点，因为更简洁。01两种情况，可以不用循环。

admin

下面看 1025 数的划分，我们用最笨的pmn来做，因为好想呀。
化成程序问题：
1-n共N个数子，选出k和，总和是n就满足条件，后面一个>=前面一个，这个和组合有点相似。
第一版，最笨的程序：

1. /// 1025
   
2. #include <iostream>
   
3. using namespace std;
   
4. const int mn=210;
   
5. const int mk=7;
   
6. int a[mk],n,k,ans=0;
   
7. void pr()
   
8. {
   
9.         int i,s=0;
   
10.         for (i=1; i<=k; i++) s+=a[i];
    
11.         if (s==n)
    
12.         {
    
13.                 cout<<++ans<<':';
    
14.                 for (i=1; i<=k; i++)  cout<<a[i]<<' ';
    
15.                 cout<<endl;
    
16.         }
    
17. }
    
18. void dfs(int i)
    
19. {
    
20.         if (i>k) pr();
    
21.         else for (int j=a[i-1]; j<=n; j++) ///k被前年用了
    
22.                 {
    
23.                         a[i]=j;
    
24.                         dfs(i+1);
    
25.                 }
    
26. }
    
27. int main()
    
28. {
    
29.         n=20,k=4; ///20 分成4 组
    
30.         a[0]=1;
    
31.         dfs(1);
    
32.         return 0;
    
33. }
    

复制代码

这个程序很笨，容易超时，但是思想是可行的，我们慢慢来优化它

admin

第一个优化，前面k-1个已经枚举出来了的话，最后一个不用枚举，只需要n-前面k-1个的和就是，加上这个优化。
第二个优化，第1个数一定不能取到n/k+1，第2个数一定不能取到n/(k-1)+1,****为什么：因为第2个数大于等于第1个，第三个大于等于第2个，要是a1>n/k+1，那么a2>n/k+1,** ak>n/k+1，全部加起来就>n了。

1. /// 1025
   
2. #include <iostream>
   
3. using namespace std;
   
4. const int mn=210;
   
5. const int mk=7;
   
6. int a[mk],n,k,ans=0;
   
7. void pr()
   
8. {
   
9.         int i,s=0;
   
10.         for (i=1; i<=k-1; i++) s+=a[i]; ///前面k-1个的和
    
11.         a[k]=n-s;
    
12.         if (a[k]>=a[k-1])
    
13.         {
    
14.                 cout<<++ans<<':';
    
15.                 for (i=1; i<=k; i++)  cout<<a[i]<<' ';
    
16.                 cout<<endl;
    
17.         }
    
18. }
    
19. void dfs(int i)
    
20. {
    
21.         if (i>k-1) pr();
    
22.         else for (int j=a[i-1]; j<=n/(k-i+1)+1; j++) ///k被前面用了
    
23.                 {
    
24.                         a[i]=j;
    
25.                         dfs(i+1);
    
26.                 }
    
27. }
    
28. int main()
    
29. {
    
30.         n=20,k=4; ///20 分成4 组
    
31.         a[0]=1;
    
32.         dfs(1);
    
33.         return 0;
    
34. }
    

复制代码

这些优化的方法是考试的重点，平常一般考搜索的话，大家都会动笔，但是谁做得好呢？差别就在优化。

admin

接上：显然，当sum>V 的时候没有必要再做了，后面的装不下呀，所以sum>V直接终止，后面的不用是搜索。
当sum==V。也不用做了，最小值就是0。（和刚才那个>有点区别）
不要在最后一起统计sum，而是每次加入新物品的时候更新sum，同时判断sum<=V

1. #include <iostream>
   
2. using namespace std;
   
3. int ans=999999;
   
4. int n,V,a[40],sum;
   
5. bool b[40];
   
6. void pr()
   
7. {
   
8.                 if (sum<=V) ans=min(ans,V-sum);
   
9. }
   
10. void dfs(int i)
    
11. {
    
12.         if (i>n) pr();
    
13.         else
    
14.         {
    
15.                 b[i]=0;  ///不选 没变化
    
16.                 dfs(i+1);
    
17.                
    
18.                 b[i]=1;///选了  
    
19.                 sum+=a[i];///总和加了
    
20.                 if (sum<=V) dfs(i+1);   ///超了 就没有下一个了！
    
21.                 sum-=a[i];///退回去
    
22.         }
    
23. }
    
24. int main()
    
25. {
    
26.         cin>>V>>n;
    
27.         for (int i=1; i<=n; i++) cin>>a[i];
    
28.         dfs(1);
    
29.         cout<<ans;
    
30. }

复制代码

admin

另外一种理解，用dfs(v,i)表示v体积下装i个物品的最小值。那么选择第i个物体，就变成了dfs(V-a(i),i+1)，不选，就是dfs(V,i+1)。