【1】题解：P5997 [PA 2014] Pakowanie【动态规划】【状压 DP】【贪心】

感觉这题放 NOIP T1 超级合适。这是一道状压 DP 的好题。首先看数据范围

n\le 24

直接起飞。然后考虑如何状压。直接转移比较困难，考虑

f_i

为前

i

个物品最少使用包数，然后设一个辅助转移的数组

g_i

为前

i

个物品目前开的最大背包。然后你发现

g

的定义不一定是对的。所以考虑把背包从大到小排序。难以处理最大背包？我们考虑到包不一定会被用完，这怎么办？我们发现当一个背包

i

可以剩余

g_i

的容量，而这个时候要是能塞下就会尽可能去塞，不会开新背包。换句话说，就是一个状态下，显然只有最大的背包对答案有影响。因为要是放不下最大的其他也放不下。那你问小物件怎么办？其实不必节省背包使用，因为放下物品一个背包不再是最大是不可能的，不然前面就已经考虑过这个物品的放置了。这就是这题的微妙之处。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=105,M=(1<<24)+5;
int a[N],b[N],n,m;
int f[M],g[M];
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<m;i++)
		cin>>b[i];
	sort(b,b+m,greater<int>());
	for(int i=1;i<(1<<n);i++)
		f[i]=m+1;
	for(int sta=0;sta<(1<<n);sta++){
		for(int i=0;i<n;i++)if((sta>>i)&1){
			int pre=sta^(1<<i);
			if(g[pre]>=a[i]){
				if(f[pre]<f[sta]||(f[pre]==f[sta]&&g[pre]-a[i]>g[sta])){
					f[sta]=f[pre];
					g[sta]=g[pre]-a[i];
				}
			}else if(b[f[pre]]>=a[i]){
				if(f[pre]+1<f[sta]||(f[pre]+1==f[sta]&&b[f[pre]]-a[i]>g[sta])){
					f[sta]=f[pre]+1;
					g[sta]=b[f[pre]]-a[i];
				}	
			}
		}
	}
	if(f[(1<<n)-1]==m+1) cout<<"NIE";
	else cout<<f[(1<<n)-1];
	return 0;
}

【1】题解：P5997 [PA 2014] Pakowanie【动态规划】【状压 DP】【贪心】

文章操作

相关推荐

评论

【1】题解：P5997 [PA 2014] Pakowanie【动态规划】【状压 DP】【贪心】