bzoj 3717: [PA2014]Pakowanie

Description

你有n个物品和m个包。物品有重量,且不可被分割;包也有各自的容量。要把所有物品装入包中,至少需要几个包?

Input

第一行两个整数n,m(1<=n<=24,1<=m<=100),表示物品和包的数量。
第二行有n个整数a[1],a[2],…,a[n](1<=a[i]<=10^8),分别表示物品的重量。
第三行有m个整数c[1],c[2],…,c[m](1<=c[i]<=10^8),分别表示包的容量。

Output

如果能够装下,输出一个整数表示最少使用包的数目。若不能全部装下,则输出NIE。

Sample Input

4 3
4 2 10 3
11 18 9

Sample Output

2

HINT

Source

鸣谢Jcvb

n很小,考虑状压;

首先背包肯定是要从大往小用的,sort一遍;

我们在dp转移的时候需要知道3个量:

用到第几个背包了,当前背包的剩余容量,已经放好的集合状态;

我们用num[zt]表示放zt的物品用到第几个背包了,用hav[zt]表示放zt的物品已经用了多少容量,sum[num[zt]-hav[zt]就是当前背包剩余的容量;

放入一个物品的转移分两种:

1.当前背包还能放,那么直接放;

2.当前背包放不了,那么新开一个背包;

//MADE BY QT666
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100050;
const int Inf=19260817;
int num[1<<24],w[200],n,m;
ll sum[200],hav[1<<24];
bool cmp(int a,int b){return a>b;}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++) scanf("%lld",&sum[i]);
sort(sum+1,sum+1+m,cmp);
for(int i=1;i<=m;i++) sum[i]=sum[i-1]+sum[i];
m=min(n,m);
for(int i=1;i<1<<n;i++) hav[i]=3e12,num[i]=Inf;
for(int zt=0;zt<1<<n;zt++){
if(hav[zt]==3e12) continue;
for(int j=0;j<n;j++){
if(!(zt&(1<<j))){
int k=zt+(1<<j);
if(sum[num[zt]]-hav[zt]<w[j+1]){
if(sum[num[zt]]+w[j+1]<hav[k]){
if(num[zt]==m||sum[num[zt]+1]-sum[num[zt]]<w[j+1]) continue;
hav[k]=sum[num[zt]]+w[j+1];
num[k]=num[zt]+1;
}
}
else{
if(hav[zt]+w[j+1]<hav[k]){
hav[k]=hav[zt]+w[j+1];num[k]=num[zt];
}
}
}
}
}
if(num[(1<<n)-1]==Inf) puts("NIE");
else cout<<num[(1<<n)-1]<<endl;
return 0;
}
上一篇:iis7/7.5设置上传文件最大大小


下一篇:智能机器人chatbot论文集合