【bzoj3717】[PA2014]Pakowanie 状压dp
DP 状压
2023-09-11 14:22:39 时间
题目描述
你有n个物品和m个包。物品有重量,且不可被分割;包也有各自的容量。要把所有物品装入包中,至少需要几个包?
输入
第一行两个整数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),分别表示包的容量。
输出
如果能够装下,输出一个整数表示最少使用包的数目。若不能全部装下,则输出NIE。
样例输入
4 3
4 2 10 3
11 18 9
样例输出
2
题解
状压dp
首先如果有解,则最多使用 $n$ 个背包,即背包数目是 $n$ 级别的,而且一定是优先选择容量最大的背包。
而按照一定的顺序装包时,选择数目较少的背包一定更优。
因此对所有背包按照容量从大到小排序,设 $f[i]$ 表示装集合 $i$ 的物品最少需要使用多少个背包, $g[i]$ 表示使用最少背包的情况下最大的剩余容量。
于是可以直接枚举每次选择的是什么物品,判断装的情况即可。
注意判断无解的情况。
时间复杂度 $O(2^n·n)$ ,由于实现有90s因此可以通过本题。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int a[24] , c[100] , f[1 << 24] , g[1 << 24]; bool cmp(int a , int b) { return a > b; } int main() { int n , m , i , j; scanf("%d%d" , &n , &m); for(i = 0 ; i < n ; i ++ ) scanf("%d" , &a[i]); for(i = 0 ; i < m ; i ++ ) scanf("%d" , &c[i]); sort(c , c + m , cmp); memset(f , 0x3f , sizeof(f)) , f[0] = -1; for(i = 1 ; i < (1 << n) ; i ++ ) { for(j = 0 ; j < n ; j ++ ) { if(i & (1 << j)) { if(g[i ^ (1 << j)] >= a[j] && (f[i ^ (1 << j)] < f[i] || (f[i ^ (1 << j)] == f[i] && g[i ^ (1 << j)] - a[j] > g[i]))) f[i] = f[i ^ (1 << j)] , g[i] = g[i ^ (1 << j)] - a[j]; if(f[i ^ (1 << j)] + 1 < m && c[f[i ^ (1 << j)] + 1] >= a[j] && (f[i ^ (1 << j)] + 1 < f[i] || (f[i ^ (1 << j)] + 1 == f[i] && c[f[i ^ (1 << j)] + 1] - a[j] > g[i]))) f[i] = f[i ^ (1 << j)] + 1 , g[i] = c[f[i ^ (1 << j)] + 1] - a[j]; } } } if(f[(1 << n) - 1] == 0x3f3f3f3f) puts("NIE"); else printf("%d\n" , f[(1 << n) - 1] + 1); }
相关文章
- POJ3080方法很多(暴力,KMP,后缀数组,DP)
- Leetcode: Combination Sum IV && Summary: The Key to Solve DP
- UVALive - 2031 Dance Dance Revolution 三维dp
- HDOJ 5418 Victor and World 状压DP
- 【Kuangbin区间DP】奶牛零食
- 【代码源区间dp】括号序列
- 【BZOJ1294】[SCOI2009]围豆豆Bean 射线法+状压DP+SPFA
- 【BZOJ3195】[Jxoi2012]奇怪的道路 状压DP
- 【BZOJ3717】[PA2014]Pakowanie 状压DP
- 【BZOJ4676】Xor-Mul棋盘 拆位+状压DP
- 【BZOJ4145】[AMPPZ2014]The Prices 状压DP
- 【BZOJ3312】[Usaco2013 Nov]No Change 状压DP+二分
- 【BZOJ1725】[Usaco2006 Nov]Corn Fields牧场的安排 状压DP
- 和与或(数位DP + 状压)
- UVa 1204 Fun Game (状压DP)
- Gym 100962J Jimi Hendrix (树形DP)
- POJ 3744 Scout YYF I (概率DP+矩阵快速幂)
- POJ 1260-Pearls(DP)
- ps dp在live video模式下播放视频
- POJ 2486 树形DP
- UVA - 825Walking on the Safe Side(dp)
- 【bzoj5161】最长上升子序列 状压dp+打表
- 【bzoj2560】串珠子 状压dp+容斥原理
- 【loj6191】「美团 CodeM 复赛」配对游戏 概率期望dp
- 【bzoj3156】防御准备 斜率优化dp