题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int n,w,ans=20,cnt=0;//cnt表示当前已经买车的数量
int a[20];//a[i]表示第i只猫的重量
int sum[20];//sum[i]表示第i辆车已经放的小猫总重量
bool cmp(int x,int y)
{
return x>y;
}
void dfs(int u)//表示当前在考虑第u只猫
{
if(cnt>=ans) return;//剪枝
if(u==n+1)
{
ans=min(ans,cnt);
return;
}
for(int i=1;i<=cnt;i++)//考虑所有已买的车
{
if(sum[i]+a[u]<=w)//可以再放一只猫
{
sum[i]+=a[u];
dfs(u+1);
sum[i]-=a[u];//回溯
}
}
//退出了for循环,则所有已买的车都不能放下这只猫,此时只能再买一辆车
cnt++;
sum[cnt]+=a[u];
dfs(u+1);
sum[cnt]-=a[u];
cnt--;
}
/*
思路:优先考虑重量大的猫(剪枝更好),先尝试能否放入已经买的
缆车内,若都放不下则再买一辆新车
*/
signed main()
{
cin>>n>>w;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n,cmp);//降序排列
dfs(1);
cout<<ans;
return 0;
}
算法2
(状压dp)
小猫爬山和此题完全一样,见ccpc秦皇岛背单词那道题
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int n,w;
int dp[1<<15];//dp[i]表示背完i的二进制表示的状态的单词所需要的最少天数
int g[1<<15];//g[i]表示状态i对应的最优方案中所有天中剩余的最大单词数
int cnt[15];
//ans=dp[(1<<n)-1];
//状态转移: dp[i]=dp[i-(1<<(j-1))]+check(j),其中j表示最后一天背的单词的长度(一定为i状态内有的单词长度)
int main()
{
cin>>n>>w;
int x;
for(int i=1;i<=n;i++)
{
cin>>x; cnt[x]++;
}
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for(int i=1;i<1<<13;i++)//枚举所有单词状态
{
for(int j=0;j<13;j++)
{
if((i>>j)&1)
{
if(g[i-(1<<j)]>=cnt[j+1])//可以合并到之前的某一天来背,不需要新开一天
{
if(dp[i]>=dp[i-(1<<j)])
{
dp[i]=dp[i-(1<<j)];
g[i]=max(g[i],g[i-(1<<j)]-cnt[j+1]);
}
}
else//此长度单词不能合并到任何一天,只能选择新开一天
{
if(dp[i]>=dp[i-(1<<j)]+1)
{
dp[i]=dp[i-(1<<j)]+1;
g[i]=max(g[i],w-cnt[j+1]);
}
}
}
}
}
cout<<dp[(1<<13)-1];//表示13种长度的单词均背时需要的最少天数
return 0;
}