无标题文档

递归剪枝算法

1 .
 
题目描述:辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有22个整数T(1 \le T \le 1000)T(1≤T≤1000)和M(1 \le M \le 100)M(1≤M≤100)，用一个空格隔开，TT代表总共能够用来采药的时间，MM代表山洞里的草药的数目。
接下来的MM行每行包括两个在11到100100之间（包括11和100100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
1个整数，表示在规定的时间内可以采到的草药的最大总价值。
样例:
输入 
70 3
71 100
69 1
1 2
输出: 
3
说明/提示
对于30%的数据，M \le 10M≤10；
对于全部的数据，M \le 100M≤100。
剪枝前算法：
 
#include<iostream>
using namespace std;
int n,m,t[101]={0},v[101]={0},s=0 ;
int f(int k,int x,int y){ //k表示当前考察到第k棵药，x表示之前还剩x时间,y表示之前已经获得价值y
	if(k>m){if(y>s)s=y;return 0;}//考察完最后一棵药，当前递归分支形成一种选择方案，判断是否更优方案，s存下更大价值y
	 if(x>=t[k]){    
	    f(k+1,x-t[k],y+v[k]);//采摘递归分支
	 }
	 f(k+1,x,y);//不采摘递归分支
}
int main(){ 
	cin>>n>>m;
	int i,j,k;
	for(i=1;i<=m;i++)cin>>t[i]>>v[i];
	f(1,n,0);
	cout<<s;
   
	return 0;
}
剪枝后算法：
 
#include<iostream>
using namespace std;
int n,m,t[101]={0},v[101]={0},s=0,p[101][1001]={0};
//p[i][j]表示考察的前i棵药还剩下有j时间的状态里各个递归分支目前阶段存下的最大价值
int f(int k,int x,int y){ 
	if(p[k][x]>=y+v[k])return 0;//如果当前第k棵药即使被采摘得到的价值y+v[k]仍然比前考察k棵药剩下x 时间的最大价值 p[k][x]还少，说明当前递归分支已经是不良递归分支，于是剪枝退出。
	 
	if(k>m){if(y>s)s=y;return 0;} 
	 if(x>=t[k]){ 
          if(y+v[k]>p[k][x-t[k]])p[k][x-t[k]]=y+v[k];//如果当前第k棵药被采摘得到的价值y+v[k]比前其他递归分支考察的前k棵药剩下x-t[k] 时间的状态里已经能得到最大价值 p[k][x-t[k]]还多，则 p[k][x-t[k]]存下当前递归分支所获得的更大的价值
	  f(k+1,x-t[k],y+v[k]); 
	 }
	 f(k+1,x,y); 
}
int main(){
    
	cin>>n>>m;
	int i,j,k;
	for(i=1;i<=m;i++)cin>>t[i]>>v[i];
	f(1,n,0);
	cout<<s;
	return 0;
}

2.
2013真题
如图1所示，3*3的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是60。

本题的要求就是请你编程判断：
对给定的m*n的格子中的整数，是否可以分割成两个部分，使得这两个区域的数字和相等。如果无法分割，则输出0。

程序输入输出格式要求：
程序先读入两个整数m,n，用两个空格分割（m,n<10）表示表格的宽度和高度。
接下来是n行，每行m个正整数，用空格分开，每个整数不大于10000。

程序输出：在所有解中，包含左上角的分割区可能包含的最小的格子数目。

例如：
用户输入：
3 3
10 1 52
20 30 1
1 2 3

则程序输出：
3

再例如：
用户输入：
4 3
1 1 1 1
1 30 80 2
1 1 1 100

则程序输出：
10
#include <iostream>

#include <algorithm>

using namespace std;

int m,n;

int total;//矩阵总和 剪格子两部分的和都应为total/2

int g[10][10];

int vis[10][10];//记录是否被访问过

int ans=100;//用于取min得最小格子数

void f(int i,int j,int sum,int cnt){//坐标会变，和会变，格子数目会变
    
  if(sum>total/2) return; //回溯 修枝
 
   if(sum==total/2){
 
       ans=min(ans,cnt);
 
       return;
    }

vis[i][j]=1;
//可以有四个分支往下走 注意边界

if(i+1<=n-1 && vis[i+1][j]==0) f(i+1,j,sum+g[i][j],cnt+1);

if(i-1>=0 && vis[i-1][j]==0) f(i-1,j,sum+g[i][j],cnt+1);

if(j+1<=m-1 && vis[i][j+1]==0) f(i,j+1,sum+g[i][j],cnt+1);

if(j-1>=0 && vis[i][j-1]==0) f(i,j-1,sum+g[i][j],cnt+1);

vis[i][j]=0;//复原访问标记

}

int main(){

scanf("%d %d",&m,&n);

for(int i=0;i<n;++i){

for(int j=0;j<m;++j){

scanf("%d",&g[i][j]);

total+=g[i][j];

}

f(0,0,0,0);

printf("%d\n",ans);

return 0;

}