证明 poj 1014 模优化修剪，部分递归 有错误
大家好，又见面了，我是全栈君
这个问题是存在做。我发现即使是可行的一个问题，但不一定正确。
大部分数据疲软，因为主题。
1.多重背包
#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;
}状态定义的是有几种方法能够转到这里来
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<iostream>
using namespace std;
int n[7]; //价值为i的物品的个数
int SumValue; //物品总价值
int HalfValue; //物品平分价值
bool flag; //标记能否平分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; //物品总价值
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;
}
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;
}这个版本号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);
} 看来学习或谨慎小心，信的过程
版权声明：本文博客原创文章，博客，未经同意，不得转载。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/117538.html原文链接：https://javaforall.cn
腾讯云开发者
