首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >计蒜客蓝桥杯模拟赛5 礼物盒

计蒜客蓝桥杯模拟赛5 礼物盒

作者头像
Max超
发布2019-01-21 15:15:34
4750
发布2019-01-21 15:15:34
举报

题目 小y 有一个宽度为 100cm,高度为 20cm,深度为 1cm 的柜子,如下图。

图一
图一

小y 还有 3636 个礼物盒,他们的深度都为 1cm。 他们对应的宽度和高度如下,单位(cm)。

图二
图二

现在小y 想把这些盒子放到柜子上,由于礼物盒里面都装有礼物,礼物盒必须向上放置,并且不能堆放。由于礼物盒深度和柜子深度一样,所以礼物盒和柜子深度方向也必须一致。并且礼物盒的高度还不能大于柜子的高度,否者放不进去。小y 希望放到柜子上礼物盒的宽度和正好等于柜子的宽度,也就是希望柜子两边都不存在间隙。如下图符合条件的放置。

图三
图三

满足条件的情况下,小y 希望能尽可能多的放置礼物盒,算出最多能放多少个礼物盒。

思路:递归

#include<iostream>
#include<algorithm>

using namespace std;

int box[36][2]={{11,3},{8,12},{11,17},{16,13},{1,14},{2,8},{6,10},{10,18},{17,11},{10,15},{6,14},{5,6},{2,19},{19,10},{4,9},{7,9},{5,14},{5,20},{15,19},{3,17},{15,11},{7,25},{11,20},{9,12},{17,4},{9,19},{4,18},{10,10},{12,19},{17,3},{19,9},{20,16},{11,16},{10,2},{20,15},{3,14}};
int x[36];
int cnt = 0;

void dfs(int num,int index,int width)
{   
    if(width == 100)
    {
        if(cnt<num)
        {
            //for(int i = 0; i < 36; i++)
            //{
            //  if(x[i])
            //  {
            //      cout << x[i] << " ";
            //  }
            //}
            //cout << endl;
            cnt = num;
        }
        return ;
    }
    if(width > 100||index==36)
    {
        return ;
    }
    if(box[index][1]<=20)
    {
        x[index] = box[index][0];
        dfs(num+1,index+1,width+box[index][0]);
        x[index] = 0;
    }
    dfs(num,index+1,width);
}
int main()
{
    dfs(0,0,0);
    cout << cnt;//18
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年04月03日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档