POJ 1664 放苹果【DFS】

浏览数：41 / 时间：2015年06月11日

题意：给出n个苹果，m个盘子，问有多少种不同的苹果放置方法

可以把它抽象为把一个数n，拆分成a1,a2,a3,---,am,使得它们的和为n,

话说这一题是学习的ppt里面的，它的思路就是搜索

搜索条件的设置：放置苹果到第k个盘子的时候，要求第k个盘子里面的苹果数目大于第k-1个盘子里面的苹果数目，如果大于，则把它放置在第k个盘子里，如果不大于，则继续放置苹果，如果剩下的苹果小于k-1个盘子里面的苹果，就停止这个分支的搜索

学搜索学的还是蒙蒙的---

这一题如果自己模拟一下样例是怎么搜的，好理解一点

7 3

分别是这8种情况

0 0 7

0 1 6

0 2 5

0 3 4

1 1 5

1 2 4

1 3 3

2 2 3

------------------------

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;
int num[10010],cnt,n,m;

void dfs(int k,int w) //k代表现在已经用了的盘子数目，w表示已经放了几个苹果 
{
	if(k==m)  //当放置到最后一个盘子的时候进行判断 
	{
		if(n-w>=num[k-1]) //如果此时剩下的苹果数大于第k-1个盘子中的苹果的数目，那么将剩下的苹果放到最后一个盘子中 
		{
			num[k]=n-w;
			cnt++;
		}
		return;
	}
		for(int i=0;i<=n;i++)
		{
			if(i>=num[k-1])
			{
				num[k]=i;
				w=w+i;
				k=k+1;
				dfs(k,w);//继续找下一个盘子放的苹果 
				w=w-i;
				k=k-1;
			}
		}
}
int main()
{
	int ncase;
	scanf("%d",&ncase);
	while(ncase--)
	{
		scanf("%d %d",&n,&m);
		cnt=0;
		dfs(1,0);//最开始的时候是一个盘子，用了0个苹果 
		printf("%d\n",cnt);
	}
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

POJ 1664 放苹果【DFS】