糖果
题目描述:一共有 $M$ 种口味的糖果,老板只卖 $K$ 颗一包的糖果。小明希望尝试所有口味的糖果,但糖果只能整包购买。给定 $N$ 包糖果,每包糖果口味各不相同,请计算小明最少需要购买多少包糖果,才能尝试到所有口味的糖果。
输入格式:第一行包含三个整数 $N, M, K$,分别表示糖果包装的数量、口味种类数以及每包的糖果数量。接下来 $N$ 行,每行包含 $K$ 个整数,表示一包糖果的口味。
输出格式:一个整数表示小明需要购买的最少糖果包装数。如果无法尝试到所有口味的糖果,则输出 -1。
样例
输入样例:
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
输出样例:
2
算法1
(暴力递归) $只能过7/11个数据$
C++ 代码
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
const int N = 105;
int n,m,k,res,s;
int a[N][N],p[N][N];
int mini = 1e5;
bool st[N];
void dfs(int u,int num,int pack,bool state[])
{
if(num==m)
{
mini = min(mini,pack);
return;
}
if(u==n || pack>=mini) return;
dfs(u+1,num,pack,state);
int x=0;
bool tmp[N]; // 保存当前状态,以便回溯时恢复
memcpy(tmp, state, sizeof(tmp)); // 备份状态数组
for(int i=0;i<k;i++)
{
if(p[u][i]==0) break;
if(state[p[u][i]] == false)
{
state[p[u][i]] = true;
x++;
}
}
dfs(u+1,num+x,pack+1,state);
memcpy(state, tmp, sizeof(tmp)); // 恢复状态数组
}
int main()
{
cin >> n >> m >> k;
for(int i=0;i<n;i++)
{
memset(st,0,sizeof st);
s= 0;
for(int j=0;j<k;j++)
{
int x;
cin >> x;
a[i][j] = x;
if(st[x]==false)
{
p[i][s] = x;
s++;
st[x]=true;
}
}
}
bool state[N];
memset(state, false, sizeof(state));
dfs(0,0,0,state);
if(mini == 1e5) cout << -1 << endl;
else cout << mini << endl;
return 0;
}
y总代码:
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 110, M = 1 << 20;
int n, m, k;
vector<int> col[N];
int log2[M];
int lowbit(int x)
{
return x & -x;
}
int h(int state) // 最少需要再选几行
{
int res = 0;
for (int i = (1 << m) - 1 - state; i; i -= lowbit(i))
{
int c = log2[lowbit(i)];
res ++ ;
for (auto row : col[c]) i &= ~row;
}
return res;
}
bool dfs(int depth, int state)
{
if (!depth || h(state) > depth) return state == (1 << m) - 1;
// 找到选择性最少的一列
int t = -1;
for (int i = (1 << m) - 1 - state; i; i -= lowbit(i))
{
int c = log2[lowbit(i)];
if (t == -1 || col[t].size() > col[c].size())
t = c;
}
// 枚举选哪行
for (auto row : col[t])
if (dfs(depth - 1, state | row))
return true;
return false;
}
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < m; i ++ ) log2[1 << i] = i;
for (int i = 0; i < n; i ++ )
{
int state = 0;
for (int j = 0; j < k; j ++ )
{
int c;
cin >> c;
state |= 1 << c - 1;
}
for (int j = 0; j < m; j ++ )
if (state >> j & 1)
col[j].push_back(state);
}
for (int i = 0; i < m; i ++ )
{
sort(col[i].begin(), col[i].end());
col[i].erase(unique(col[i].begin(), col[i].end()), col[i].end());
}
int depth = 0;
while (depth <= m && !dfs(depth, 0)) depth ++ ;
if (depth > m) depth = -1;
cout << depth << endl;
return 0;
}
算法2
(动态规划DP) $O(n*2m)$
//状态表示:dp[i][s]为从前i个糖果中选,选出来的糖果种类状态为s的所需最少糖果数量
//阶段划分:类似于01背包问题中,从前i个物品中选
//转移方程:划分依据:对于第i个物品选还是不选
//dp[i][s] = min(dp[i-1][s],dp[i-1][s & (~w[i])] + 1)
//dp[i-1][s]好说 表示不选第i个物品
//关键是dp[i-1][s & (~w[i])],举个例子若现在s为 11011,表示已经选出来的糖果种类为1,2,8,16
//假设第i包糖果的状态为01011,那么他是从10000这个状态转移过来的
//那么s & (~w[i])的目的就是先将w[i]的糖果种类去掉,~w[i]按位取非,在与s相于就行了,实质上就是s & (w[i]在s中的补集)
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110,M = 1 << 20,INF = 0x3f3f3f3f;
int w[N],dp[M],n,m,k;//注意优化成一维不然暴空间
int main(void)
{
cin>>n>>m>>k;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=k;j++)
{
int num;
cin>>num;
w[i] |= (1 << num - 1);//将每一件糖果所包含的糖果种类压缩
}
memset(dp,0x3f,sizeof dp);
dp[0] = 0;
for(int i = 1;i<=n;i++)
for(int s = 0;s < (1 << m);s ++) dp[s] = min(dp[s],dp[s & (~w[i])] + 1);
if(dp[(1<<m)-1] == INF) cout<<-1<<endl;
else cout<<dp[(1<<m) - 1]<<endl;
return 0;
}
AcWing《CCF-CSP认证辅导课》拼团优惠!https://www.acwing.com/activity/content/introduction/39/group_buy/205418/