It is proved that POJ 1014 module is optimized and pruned, and some recursion is wrong

Hello everyone , I meet you again , I'm the king of the whole stack

The problem is to do . I found that even a feasible problem , But not necessarily right .

Most of the data is weak , Because of the theme .

1. Multiple backpack

#include <map>
#include<string>
#include <iostream>
#include<stack>
#include<algorithm>
#include <math.h>
using namespace std;
#define MAXN 100+60000
int v[MAXN];
int a[MAXN/3];
int b[7] = {1, 60, 30, 20, 15, 12, 10};
int N,T,n,sum;
/*int direct[4][2]={-1,0,1,0,0,-1,0,1};
 int dp[210][210][210];*/
int max(int a,int b)
{
	return a>b?a:b;
}


int main()
{
	int i,j,k,flag,casenum;
	casenum=0;
	while(1)
	{
		casenum++;
		memset(v,0,sizeof(v));
		flag=0;
		sum=0;
		n=0;
		for(i=0;i<6;i++)
		{
			scanf("%d",&k);
			if(k)
				flag=1;
			k=k%b[i+1];
			sum+=k*(i+1);
			for(j=1;j<=k;j++)
				a[n++]=i+1;
		}
		if(flag==0)
			break;
		if(sum&1)
		{
			printf("Collection #%d:\nCan't be divided.\n\n",casenum);
			continue;
		}
		flag=0;
		sum/=2;
		v[0]=1;
		for(i=0;i<n;i++)
		{
			for(j=sum;j>=a[i];j--)
			{
				v[j]+= v[j-a[i]];
				if(v[sum])
				{
					flag=1;break;
				}
				if(flag)
					break;
			}
		}
		if(flag)
			printf("Collection #%d:\nCan be divided.\n\n",casenum);
		else
			printf("Collection #%d:\nCan't be divided.\n\n",casenum);
		
	}
	
	return 0;
}

Copy

The definition of state is that there are several ways to go here

k=k%b[i+1];

This sentence is an optimization , At first I saw , Think it's very wonderful , But I don't understand why I can do this .

It turned out to be wrong , The proof is as follows ：

Modular optimization is wrong , The following proves the case of optimizing a pile 1.1a+2b+3c+4d+5e+6f 2.60*m*t+ 1a+2b+3c+4d+5e+6f（t It is the number of stones in a pile ,m Is the weight of a pile of stones ） Proving that the optimization is correct proves 1 yes 2 Formula is a necessary and sufficient condition When 1 When it was founded , Naturally get 2 establish （60 Can be divided into two piles ） When 2 There are two cases of establishment , Case one ,2 Divisible ,1 The part of itself can be divided , that 60*m*t This part should have been divided Another situation .2 Divisible .1 The part of itself cannot be divided , You need to 60*m*t It is feasible to divide this part into two parts This proves that it is infeasible to split one , However, it is not ruled out that every heap will be optimized, and it will happen to be feasible Finally, I give you an example 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

Optimize or use 2 Binary method optimization （1,2,4,…,2^(k-1),n[i]-2^k+1, And k Is to meet n[i]-2^k+1>0 Maximum integer for .

such as . hypothesis n[i] by 13. The partition coefficients of such items are 1,2,4,6 Four items of ）

1. Why are some transfer equations on the Internet v[i][j]=max(v[i-1][j],v[j-a[i]]+a[i])?
2. answer ： Be able to see j-a[i] Show and a[i] Complementary state , In fact, it is j, From all J Point of view . It hasn't changed , This is a v[0]=0

2. dfs Version number （ Reprinted in Daniel Blog）

//Memory Time 
//452K 0MS 

/*DFS*/

#include<iostream>
using namespace std;

int n[7];  // Value is i Number of items 
int SumValue;  // Total value of goods 
int HalfValue;  // Divide the value of the goods equally 
bool flag;    // Whether the mark can be divided equally SumValue

void 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;  // Total value of goods 

		for(i=1;i<=6;i++)
			SumValue+=i*n[i];

		if(SumValue==0)
			break;

		if(SumValue%2)    //sum It's odd , Cannot be divided equally 
		{
			cout<<"Collection #"<<test++<<':'<<endl;
			cout<<"Can't be divided."<<endl<<endl;    // Pay attention to the space 
			continue;
		}

		HalfValue=SumValue/2;
		flag=false;

		DFS(0,6);

		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;
}

Copy

This version number dfs It's very good , among This depth first has two advantages worth considering

1. Why is there no backtracking . Instead, the quantity is directly subtracted n[i]–;

answer ： Two people choose , It must be divided into two parts , Suppose you don't choose the closest number , The rest is closer

2. Choose from big to small ？

answer ： There may be several small ones that can be directly replaced by a large number

———————————————————————————————————————————-

But there are problems .

Its essence is the use of greedy strategies , But I can't satisfy some “ jumping ” The requirements of

eg: 0 0 3 0 3 1 The numbers to be selected are discontinuous , In fact, there should be backtracking .

To avoid this problem, you can use this version number

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);  
}  

Copy

It seems that study or be careful , The process of letter

Copyright notice ： This article is an original blog article , Blog , Without consent , Shall not be reproduced .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/117538.html Link to the original text ：https://javaforall.cn