DFS(DP)---POJ 1014(Dividing)

2024-06-14 08:32
文章标签 dp poj dfs 1014 dividing

本文主要是介绍DFS(DP)---POJ 1014(Dividing),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题目:http://poj.org/problem?id=1014

题目大意

有分别价值为1,2,3,4,5,66种物品,输入6个数字,表示相应价值的物品的数量,问一下能不能将物品分成两份,是两份的总价值相等,其中一个物品不能切开,只能分给其中的某一方,当输入六个0是(即没有物品了),这程序结束,总物品的总个数不超过20000

 


输出:每个测试用例占三行:

           第一行: Collection #k: k为第几组测试用例

           第二行:是否能分(具体形式见用例)

           第三行:空白(必须注意,否则PE



:采用第一种深搜方式,如果sum<halfvalue继续往下探索,如果大于则回溯到上一层,证明上一层选的不合适。认真分析就会发现问题,(1)这个树中的搜索路径很明显不支持同一个数字的若干次选取。(2)仅仅只有六层。这怎么可以呢!照此说不管怎么遍历都是1+2+3+4+5+6.

 

这种搜索是合理的。每次探测都可以有六种选择,也可以想象成从六个盒子里面拿东西,每次从六个盒子里选一种,第一种出现的两种错误都可以避免掉。而且每个节点的度都是6,而且特征一样。这个非常好,对每个节点的处理都一样。很明显可以递归。符合DFS的特点。


解题思路:

有两种解决方法:

第一种是几乎百度上所有同学都热衷的多重背包,确实这题就是《背包九讲》里面的“多重背包”的应用题,直接套O(V*Σlog n[i])的模板就毫无悬念地AC了,《背包九讲》里面提供的是“多重背包+二进制优化”算法,百度上也有不少同学加入了自己的想法去进一步优化,例如利用“抽屉原理”证明并“取模优化”的可行性等,这些同学都做了不少功课,值得我们学习。

 

    第二种方法是几乎没有同学使用的DFS,本题用DFS也能0ms跑完,可能大家都被《背包九讲》冲昏了头脑,都想着套模板去了,但又看不懂模板。呻吟“研究了背包多长时间都不完全明白”的同学不妨试试DFS。其实本来不少DP题都可以用搜索过的,大家不要钻牛角尖。

解法一:DFS

#include<iostream>
using namespace std;int amount[7] = {0};
int half_value = 0;
int flag = 0;void DFS(int value, int pre){if(value == half_value){flag = 1;return;}if(flag == 1){	// 到某一深度的时候接受到上层的(flag=1),那这层也要继续往上return;}int i = 0;for(i = pre; i > 0; i--){if(amount[i]){if(i + value <= half_value){amount[i]--;DFS(i + value, i);
<span style="white-space:pre">						</span>//如果搜索到某一深度满足条件if(flag == 1){	//回到上层return;}}}}
}int main(){int testcase = 1;while(true){flag = 0;int totalvalue = 0;int N = 6;int i = 1;while(i <= N){cin >> amount[i];totalvalue += amount[i] * i;i++;}if(!amount[1] && !amount[2] && !amount[3] && !amount[4] && !amount[5] && !amount[6]){break;}printf("Collection #%d:\n", testcase++);if(totalvalue % 2 != 0){cout << "Can't be divided." << endl << endl;continue;}half_value = totalvalue / 2;DFS(0, 6);		//注意由于6的价值比较大容易接近所要得的一半
<span style="white-space:pre">					</span>//若取1可能会多走很多if(flag){cout << "Can be divided." << endl;} else {cout << "Can't be divided." << endl;}cout << endl;}	return 0;
}


(上面这个代码有个bug(题目还是可以AC的)( 0 0 3 0 3 1) 就过不了,上面是不能跳过中间值的,

而数据是要6和3结合于是就呵呵了(求大牛赐教怎么修改)



当然还有解法二:

//Memory Time 
//656K  16MS /*多重背包+二进制优化*/#include<iostream>
using namespace std;int n[7];  //价值为i的物品的个数
int v;  //背包容量
int SumValue;  //物品总价值
bool flag;    //标记是否能平分SumValue
int dp[100000];  //状态数组int max(int a,int b)
{return a>b?a:b;
}/*完全背包*/
void CompletePack(int cost,int weight)
{for(int i=cost;i<=v;i++){dp[i]=max(dp[i],dp[i-cost]+weight);if(dp[i]==v)    //剪枝,当能够平分SumValue时退出{flag=true;return;}}return;
}/*01背包*/
void ZeroOnePack(int cost,int weight)
{for(int i=v;i>=cost;i--){dp[i]=max(dp[i],dp[i-cost]+weight);if(dp[i]==v)    //剪枝{flag=true;return;}}return;
}/*多重背包*/
void MultiplePack(int cost,int weight,int amount)
{if(cost*amount>=v){CompletePack(cost,weight);return;}if(flag)    //剪枝return;/*二进制优化*/int k=1;while(k<amount){ZeroOnePack(k*cost,k*weight);if(flag)    //剪枝return;amount-=k;k*=2;}ZeroOnePack(amount*cost,amount*weight);return;
}int main(int i)
{int test=1;while(cin>>n[1]>>n[2]>>n[3]>>n[4]>>n[5]>>n[6]){SumValue=0;  //物品总价值for(i=1;i<=6;i++)SumValue+=i*n[i];if(SumValue==0)break;if(SumValue%2)    //sum为奇数,无法平分{cout<<"Collection #"<<test++<<':'<<endl;cout<<"Can't be divided."<<endl<<endl;    //注意有空行continue;}v=SumValue/2;memset(dp,-1,sizeof(dp));dp[0]=0;flag=false;for(i=1;i<=6;i++){MultiplePack(i,i,n[i]);if(flag)    //剪枝break;}if(flag){cout<<"Collection #"<<test++<<':'<<endl;cout<<"Can be divided."<<endl<<endl;continue;}else{cout<<"Collection #"<<test++<<':'<<endl;cout<<"Can't be divided."<<endl<<endl;continue;}}return 0;
}


这篇关于DFS(DP)---POJ 1014(Dividing)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1059891

相关文章

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];