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

ExFish · 2025-11-23 22:26:45 · 题解

感觉这题放 NOIP T1 超级合适。这是一道状压 DP 的好题。首先看数据范围 n\le 24 直接起飞。然后考虑如何状压。直接转移比较困难，考虑 f_i 为前 i 个物品最少使用包数，然后设一个辅助转移的数组 g_i 为前 i 个物品目前开的最大背包。然后你发现 g 的定义不一定是对的。所以考虑把背包从大到小排序。难以处理最大背包？我们考虑到包不一定会被用完，这怎么办？我们发现当一个背包 i 可以剩余 g_i 的容量，而这个时候要是能塞下就会尽可能去塞，不会开新背包。换句话说，就是一个状态下，显然只有最大的背包对答案有影响。因为要是放不下最大的其他也放不下。那你问小物件怎么办？其实不必节省背包使用，因为放下物品一个背包不再是最大是不可能的，不然前面就已经考虑过这个物品的放置了。这就是这题的微妙之处。

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