[USACO12MAR] Cows in a Skyscraper G
2025年2月26日大约 2 分钟
暴力搜索 32 分
枚举每个物品放到了哪组
#include <bits/stdc++.h>
using namespace std;
int n, w;
int x[18 + 5];
int v[18 + 5];
int ans;
// 当前物品,已有分组组数
void dfs(int pos, int cnt)
{
if (pos == n + 1)
{
ans = min(ans, cnt);
return;
}
for (int i = 1; i <= cnt; i++)
{
if (v[i] + x[pos] <= w)
{
v[i] += x[pos];
dfs(pos + 1, cnt);
v[i] -= x[pos];
}
}
v[cnt + 1] = x[pos];
dfs(pos + 1, cnt + 1);
v[cnt + 1] = 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> x[i];
ans = n + 1;
dfs(1, 0);
cout << ans;
return 0;
}
剪枝 100 分
不如最优结果时就不看了
#include <bits/stdc++.h>
using namespace std;
int n, w;
int x[18 + 5];
int v[18 + 5];
int ans;
// 当前物品,已有分组组数
void dfs(int pos, int cnt)
{
if (cnt >= ans)
return;
if (pos == n + 1)
{
ans = min(ans, cnt);
return;
}
for (int i = 1; i <= cnt; i++)
{
if (v[i] + x[pos] <= w)
{
v[i] += x[pos];
dfs(pos + 1, cnt);
v[i] -= x[pos];
}
}
v[cnt + 1] = x[pos];
dfs(pos + 1, cnt + 1);
v[cnt + 1] = 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> x[i];
ans = n + 1;
dfs(1, 0);
cout << ans;
return 0;
}
状压 DP
f[i][sta]
表示 i
组,选了 sta
这些物品,其中体积最小的那组的体积。
如果有了一个这样的合法的状态,就可以考虑塞一个新物品能否达成就要么放到最小的那组,要么新开一组。
新开一组的转移很好理解。如果放到最小的那组,显然就需要考虑每个物品放到“剩下所有物品中最小的那组”后的体积,这每个体积都是能达成的最小体积,这些最小体积中的最小值肯定就是最优的了。
#include <bits/stdc++.h>
using namespace std;
int n, w;
int a[20];
int f[20][300000];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> a[i];
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= (1 << n) - 1; j++)
{
if (f[i][j] != 0x3f3f3f3f)
{
for (int k = 0; k <= n - 1; k++)
{
if (j & (1 << k))
continue;
if (f[i][j] + a[k + 1] <= w)
f[i][j + (1 << k)] = min(f[i][j + (1 << k)],
f[i][j] + a[k + 1]);
else
f[i + 1][j + (1 << k)] = min(f[i + 1][j + (1 << k)],
a[k + 1]);
}
}
}
}
for (int i = 0; i <= n; i++)
if (f[i][(1 << n) - 1] != 0x3f3f3f3f)
{
cout << i << endl;
break;
}
return 0;
}