箱子装货物问题

#Robot Sends Red Packets

> https://ac.nowcoder.com/acm/contest/8829/E

n个硬币分成若干堆，每堆硬币的价值相同，求最堆最小价值的分配方案。思路：三层dfs剪枝.

#include<bits stdc++.h>

using namespace std;
typedef long long ll;

ll dp[100][2];
int sum=0;
int b[100],a[100];
int m;
int n; 

vector<int> gg;

bool f; 
int cnt=0;
bool vis[70];
int all;

bool dfs( int x ,int up ,int last )
{
	if( x&gt;cnt ) return true;
	if( up==all ) return dfs(x+1,0,1);
	
	int fail=0;
	for( int i=last;i&lt;=n;i++ )
	{
		if( !vis[i] &amp;&amp; up+a[i]&lt;=all &amp;&amp;  fail!=a[i] ) 
		{
			vis[i]=1;
			if( dfs(x,up+a[i],i+1) ) return true;
			fail=a[i];
			vis[i]=0;
			if( up==0 || up+a[i]==all ) return false;
		}
	}
	return false;
}

int main()
{
//	freopen("1.in","r",stdout);
//	freopen("1.out","w",stdin);
	int t;
	scanf("%d",&amp;t);
	while( t-- )
	{
		
		scanf("%d",&amp;n);
		sum=0;
		int maxs=0;
		for( int i=1;i&lt;=n;i++ ) scanf("%d",&amp;a[i]),sum+=a[i],maxs=max(a[i],maxs);
		sort(a+1,a+1+n,[&amp;]( int x,int y){return x&gt;y;} );
		bool d=0;
		
		vector<int> dd;
		for( int i=n;i&gt;=1;i-- )
		{
			if( sum%i==0 ) dd.push_back(i);
		}
		
		for( int i:dd )
		{
			cnt=i;
			all=sum/i;
			memset(vis,0,sizeof(vis));
			if( dfs(1,0,1) ) 
			{	
	   			cout&lt;<sum i<<"\n"; break; 
            }
 }
/* 
1 53 38 22 9 16 10 5 4 26 43 56 11 46 23 36 55 21 50 64 19 15 17 66 32 54 39 20 45 41 27 25 33 58 61 60 35 
*/

装货物>https://ac.nowcoder.com/acm/contest/3781/C

有 $图片说明$ 件货物，第 $图片说明$ 件重吨，另有 $图片说明$ 个集装箱，每个集装箱可以装重量不超过 $图片说明$ 吨的货物。货物不能分拆，请判断这 $图片说明$ 个集装箱能否装下所有货物。

分析：参考出题人题解 https://ac.nowcoder.com/discuss/361552?type=101&order=0&pos=1&page=1&channel=666&source_id=discuss_tag

定义两个状态 $图片说明$ $图片说明$ 表示拿的物品状态为 $图片说明$ (二进制下01表示是否装入 )下最少箱子数。 $图片说明$ 表示拿的物品状态为 $图片说明$ (二进制下01表示是否装入 )下最少箱子数方案中一个箱子的最大剩余量。那么外层循环遍历所有装物品的状态，内层循环依次找到未装入箱子的物品，进行转移。对于当前状态 $图片说明$ 和该状态下未装入箱子的物品 $图片说明$ ,如果放入物品 $图片说明$ 那么要对 $图片说明$ 进行更新。更新的条件分成两种. 1. $图片说明$ $图片说明$ 就是当前 $图片说明$ 状态下放入 $图片说明$ 物品最少装箱数不变的,进行更新。(贪心策略求得 $图片说明$ 尽可能小， $图片说明$ 尽可能大) 2 $图片说明$ 就是当前 $图片说明$ 状态下增加一个箱子放入 $图片说明$ 物品最少装箱数小于等于 $图片说明$ 状态的最小装箱数.

#include<bits stdc++.h>
using namespace std;

int n,W,x,w[21],dp1[1&lt;&lt;21],dp2[1&lt;&lt;21];
int p[25];

int main()
{
	for( int i=p[0]=1;i&lt;=21;i++ ) p[i]=p[i-1]&lt;&lt;1;
	int T;
	cin&gt;&gt;T;
	while( T-- )
	{
		scanf("%d%d%d",&amp;n,&amp;x,&amp;W);
		for( int i=0;i<n;i++ ) scanf("%d",w+i); if( *max_element(w,w+n)>W ) 
		{
			puts("No");
			continue;
		} 
		memset(dp1,0x3f,4*(1&lt;<n)); memset(dp2,0,4*(1<<n)); dp1[0]="1,dp2[0]=W;" for( int i ) { j="0;j<n;j++" if( & p[j] continue; dp2[i]>=w[j] &amp;&amp; dp1[i|p[j]]&gt;=dp1[i] )
				{
					dp1[i|p[j]]=dp1[i];
					dp2[i|p[j]]=max(dp2[i|p[j]],dp2[i]-w[j]);
				}
				else if( dp1[i|p[j]]&gt;=dp1[i]+1 )
				{
					dp1[i|p[j]]=dp1[i]+1;
					dp2[i|p[j]]=max(dp2[i|p[j]],W-w[j]);
				}
			}
		}
		puts( dp1[p[n]-1]&lt;=x ? "Yes" : "No");
	}
	return 0;
}

后附上一个快速过水数据的dfs爆搜

#include<bits stdc++.h>
using namespace std;
 
typedef long long ll;
const int maxn=100;
int n,c;
ll w;
ll a[maxn],b[maxn];
 
bool dfs( int u )
{
    if( u==n ) return true;
    for( int i=0;i<min(c,u+1);i++ ) { if( b[i]+a[u]<="w" b[i]+="a[u];" dfs(u+1) return true; b[i]-="a[u];" } false; void solve() cin>&gt;n&gt;&gt;c&gt;&gt;w;
    memset(b,0,sizeof(b));
    for( int i=0;i<n;i++ ) cin>&gt;a[i];
    if( dfs(0) ) puts("Yes");
    else puts("No");
}
 
int main()
{
    int t;
    cin&gt;&gt;t;
    while( t-- ) solve();
    return 0;
}

后续继续：原题链接 >https://www.luogu.com.cn/problem/P3052 看完评论又学了一手模拟退火(~~退火邪教~~ 模拟退火：还没调出AC的参数.... 附一份过92.31%的代码

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cstdlib> 
#include<algorithm> 
using namespace std;
long long f[22]; 


double t,tmin=1e-8;
double delta=0.9991;
double ans=21;
int w,n;

inline long long read( long long &amp;x )
{
	x=0;
	int f=1;char s=getchar();
	for( ;!isdigit(s);s=='-' &amp;&amp; (f=-1),s=getchar());;
	for( ;isdigit(s);x=x*10+s-48,s=getchar());
	return x*f;
}


inline int solve()
{
	int res=1,sum=0;
	for( int i=1;i&lt;=n;i++ )
	{
		if( sum+f[i]&lt;=w ) sum+=f[i];
		else res++,sum=f[i];
	}
    return res;
}

void sa()
{
    t=3000;double now=ans;
    
    while(t&gt;tmin)
    {
        int x=rand()%n+1;
        int y=rand()%n+1;
        while( x==y ) x=rand()%n+1,y=rand()%n+1; // main 要特判 n=1 的情况 
        swap(f[x],f[y]);
        
        int pos=solve();
        
        double delta2=(double)pos-now;
        if( delta2&lt;0 ) ans=now=pos;
        else if( exp( -delta2/t )*RAND_MAX&gt;rand());
        else swap(f[x],f[y]);
        t*=delta;
    }
}

int main()
{   
	int t;
	scanf("%d",&amp;t);
	while( t-- )
	{
		srand(19491001);srand(rand());srand(rand());
	    int x;
	    scanf("%d%d%d",&amp;n,&amp;x,&amp;w);
	    for(register int i=1;i&lt;=n;i++ ) read(f[i]);
	    if( *max_element(f+1,f+1+n)&gt;w ) 
	    {
	    	puts("No");
	    	return 0;
	    }
	    if( n==1 )
	    {
	    	puts("Yes");
	    	return 0;
	    }
	    
	    ans=solve();
	    int last=ans;
	    for( int i=1;i&lt;=50;i++ ) 
	    {
	    	sa();
	    	last=min(last,(int)ans);
	    }
	    
	    if( last&lt;=x ) puts("Yes");
	    else puts("No");
	} 
}

</n;i++></min(c,u+1);i++></n));></n;i++>