前言

最近在牛客网上找了点阿里巴巴笔试的编程题做，现在做个简单的总结。有的代码还在调，会慢慢发出来。有的问题可以直接暴力破解的就不放出来了，一般那种问题几层循环就解决了。不过笔试编程对时间和空间都有要求，有的题可能会过不了。如果题目本身比较有意义，我也会放到下面。

题目 1：

问题描述：小明在双十一晚会上抽奖赢得了一次天猫超市免单的机会，享受在一个包裹内最大体积V，最大重量M内免单。假设商品i，体积Vi，重量Mi，库存Si，价格Pi目前天猫超市的商品分为生鲜水产(1)、食品酒水(2)、美妆个护(3)和居家生活(4)四大类，且生鲜水产不与美妆个护同包裹，请你帮助小明在购物车里添置商品使得总价值最大。

首先这个用例是错误的，我也是编完程才发现的。官方给的用例结果是33，很明显就是第二种商品拿3个。但事实，要想达到最大价值，需要取第三种商品5个，再拿一个第二种商品，此时volume = 28，wight = 30，value = 36符合要求。

解题思路：刚开始时，我一直在纠结两个物品不能同包裹这一条件，所以将问题想的太复杂了。后来发现，我完全可以创建 2 个vector，一个放水产和其他物品，另一个放美妆和其他物品。最后通过取两种情况的最大价值便可以得到答案。通过上面的思路，将问题转换成类似0-1背包问题。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;struct goods
{int wight;   //物品重量int volume;  //物品体积int value;   //物品价值
};int goodssuma1 = 0, goodssuma2 = 0;      //用来记录向量的长度
int Bagvolume,Bagwight,bestValue = 0;    //代表包裹的容量和能承受的重量
int Cvalue,Cwight,Cvolume;               //代表目前的价值，质量和容量
vector<goods> a1, a2;                    //a1放水产+其他商品，a2放美妆+其他商品int Force(int i, const vector<goods> &x, int goodssum){if(i > goodssum-1){if(bestValue < Cvalue && Cwight <= Bagwight && Cvolume <= Bagvolume)bestValue = Cvalue;return bestValue;}Cwight = Cwight + x[i].wight;                    //拿这件商品Cvalue = Cvalue + x[i].value;Cvolume = Cvolume + x[i].volume;if(Cwight <= Bagwight && Cvolume <= Bagvolume)   //超过任一要求就不需要再往下递归了Force(i+1, x, goodssum);Cwight = Cwight - x[i].wight;                    //不拿这件商品Cvalue = Cvalue - x[i].value;Cvolume = Cvolume - x[i].volume;if(Cwight <= Bagwight && Cvolume <= Bagvolume)Force(i+1, x, goodssum);return bestValue;
}int main()
{int goodsnum,goodsvolume, goodswight, goodsn, goodsvalue, number, maxsum;goods asd;printf("物品种类、最大体积及最大重量：");scanf("%d,%d,%d", &goodsnum, &Bagvolume, &Bagwight);while(goodsnum--){//商品输入是：体积，重量，库存，价钱 和 商品编号printf("输入数据:");scanf("%d,%d,%d,%d,%d", &goodsvolume, &goodswight, &goodsn, &goodsvalue, &number);asd.wight = goodswight;asd.volume = goodsvolume;asd.value = goodsvalue;if(number == 1){while(goodsn--)a1.push_back(asd);}else if(number == 3){while(goodsn--)a2.push_back(asd);}else{while(goodsn--){a1.push_back(asd);a2.push_back(asd);}}}goodssuma1 = a1.size();goodssuma2 = a2.size();int sum1 = Force(0, a1, goodssuma1);bestValue = 0;    Cvalue = Cwight = Cvolume = 0; int sum2 = Force(0, a2, goodssuma2);if(sum1 > sum2)maxsum = sum1;elsemaxsum = sum2;printf("装入最大总价值[%d]\n",maxsum);return 0;
}

题目 2：

问题描述：

有一个整数n，你需要经过若干次操作，使 n 不小于 m。可以对n完成以下操作：

操作1：将n变更为 2*n ，花费为w2；

操作2：将n变更为 3*n ，花费为w3。

当满足n不小于m时，输出最小花费。

输入描述：

输入第一行一个整数 T，代表测试 T 组数据。接下来 T 行，每行有4个整数，n， m， w2， w3。其中 1 <= T <= 10000， 1 <= n,m <= 2^(31) - 1， 1 <= w2,w3 <= 1000。

输出：

对于每组数据，输出一个整数代表最小花费。

input：
1  6  2  3
4  32 3  4
2  1  1  2
1  2147483647  1  4output：
5
9
0
31

解题思路：这两道题都是在求最优解，思路很相似，但是问题 2相对而言复杂一点。一方面是因为原题题干给的信息很难读懂，另一方面原因是原题输出的第二个示例答案给的是 8 ，正确答案应该是 9。这导致我开始没有理解题目的意思，编程半小时，调试一整天，最后还得不到正确答案。当时人都崩溃了。发现不对后又开始重新看题，捋清楚题干后总算是把题做出来了，第二道题就花了我 2 天时间(太难受了)。

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;int w2,w3,Ccount = 0;
int bestcount = 999;
long n,m;int asd(int i)
{if(i == 0 && n >= m)return 0;if(n < m){n *= 2;Ccount = Ccount + w2;if(n >= m && bestcount > Ccount){bestcount = Ccount;return bestcount;}elseasd(i+1);n /= 2;Ccount = Ccount - w2;n *= 3;Ccount = Ccount + w3;if(n >= m && bestcount > Ccount){bestcount = Ccount;return bestcount;}elseasd(i+1);n /= 3;Ccount = Ccount - w3;}//if(n < m) endreturn bestcount;
}int main()
{int times, value;cin >> times;while(times--){cin >> n >> m >> w2 >> w3;value = asd(0);Ccount = 0;bestcount = 999;           //就是因为忘了重置，让我调试了半天cout << value <<endl;}	return 0;
}

阿里巴巴(Alibaba)笔试编程题

前言

题目 1：

题目 2：