这个问题是存在做。我发现即使是可行的一个问题，但不一定正确。

大部分数据疲软，因为主题。

题目大意：有6堆石头，权重分别为1 2 3 4 5 6，要求输入 每堆个数 ，求能否够平分石头使得两堆价值同样。

网上对这道题的做法就两种，当中有错误的版本号。却也能够AC。

起初这让我等菜鸟感慨代码的简洁，但无法得出正确性的证明

接下来就对两种方法的错误性进行证明。

1.多重背包

#include 

状态定义的是有几种方法能够转到这里来

k=k%b[i+1];

这句是一种优化，起初看到，认为非常奇妙，但并不理解为什么能够这样做。

后来证明是错误的，证明例如以下：

取模优化是错误的，以下证明优化一堆的情况

1.1a+2b+3c+4d+5e+6f

2.60*m*t+     1a+2b+3c+4d+5e+6f（t是某堆石子的个数,m是某堆石子的权重）

证明优化正确即证明1 是 2 式是充分必要条件

当1成立时候，自然得到2成立（60能够分到两堆）

当2成立有两种情况，

第一种情况，2可分，1的部分本身可分，那么60*m*t 这部分本来分掉就好

另外一种情况。2可分。1的部分本身不可分，须要将60*m*t这部分拆解分到两人才可行

由此得证将某个拆分掉是不可行的，可是不排除每堆都优化会遇到碰巧可行的情况

最后举个样例给大家

1. 0 0 0 0 66 5 -> 0 0 0 0 6 5   ture

2. 60 0 0 0 0 1 -> 0 0 0 0 0 1   fault

优化还是用2进制的方法优化吧（1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。

比如。假设n[i]为13。就将这样的物品分成系数分别为1,2,4,6的四件物品）

为何网上有些转移方程为v[i][j]=max(v[i-1][j],v[j-a[i]]+a[i])?
答：能够看到j-a[i]表明与a[i]互补的状态，事实上为j，从全部的J角度来看。并未改变，这是v[0]=0

2. dfs版本号（转载于大牛Blog）

//Memory Time //452K 0MS /*DFS*/#include
     
      using namespace std;int n[7];  //价值为i的物品的个数int SumValue;  //物品总价值int HalfValue;  //物品平分价值bool flag;    //标记能否平分SumValuevoid DFS(int value,int pre){	if(flag)		return;	if(value==HalfValue)	{		flag=true;		return;	}	for(int i=pre;i>=1;i--)	{		if(n[i])		{			if(value+i<=HalfValue)			{				n[i]--;				DFS(value+i,i);				if(flag)					break;			}		}	}	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 #"<
      
       <<':'<
      
     

这个版本号dfs写的非常好，当中

这个深度优先有两个长处值得思量

1.为什么没有回溯。而是直接减去了数量n[i]--;

答：两个人选择，必定是将这部分分为两份，假设不选择到最接近的数字，那剩余的则是更接近的

2.从大到小选择？

答：可能有多个小的能够用一个大的数字直接替换掉

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

可是存在问题。

其本质是使用了贪心的策略，但无法满足有些“跳跃”的要求

eg: 0 0 3 0 3 1  须要选取的数字是不连续的，事实上还要有回溯的。

避免这个问题能够用这个版本号

void divide(int cur_value, int cur_index)  {          // set break point          if (flag)                  return;          if (cur_value == half_value)          {                  flag = true;                  return;          }          if (cur_value > half_value || cur_index >= max_index)                  return;          divide(cur_value+array[cur_index], cur_index+1);          divide(cur_value, cur_index+1);  }

看来学习或谨慎小心，信的过程

版权声明：本文博客原创文章，博客，未经同意，不得转载。