签名能留链接的网站,数据库网站建设公司,免费动态图片素材网站,最新裁员公司名单题目描述
达达帮翰翰给女生送礼物#xff0c;翰翰一共准备了 N N N 个礼物#xff0c;其中第 i i i 个礼物的重量是 G [ i ] G[i] G[i]。
达达的力气很大#xff0c;他一次可以搬动重量之和不超过 W W W的任意多个物品。
达达希望一次搬掉尽量重的一些物品#xff0c;请…题目描述
达达帮翰翰给女生送礼物翰翰一共准备了 N N N 个礼物其中第 i i i 个礼物的重量是 G [ i ] G[i] G[i]。
达达的力气很大他一次可以搬动重量之和不超过 W W W的任意多个物品。
达达希望一次搬掉尽量重的一些物品请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数分别代表 W W W 和 N N N。 以后 N N N行每行一个正整数表示 G [ i ] G[i] G[i]。
输出格式
仅一个整数表示达达在他的力气范围内一次性能搬动的最大重量。
数据范围 1 ≤ N ≤ 46 1≤N≤46 1≤N≤46, 1 ≤ W , G [ i ] ≤ 2 31 − 1 1≤W,G[i]≤2^{31}−1 1≤W,G[i]≤231−1
输入样例
20 5
7
5
4
18
1输出样例
19算法思想
根据题目描述需要从给定的 N N N个数中选择几个使它们的和最接近 W W W属于“子集和”问题的扩展当然也可以从背包问题的角度去思考解决但是这里背包的“体积”过大 1 ≤ W ≤ 2 31 − 1 1≤W≤2^{31}−1 1≤W≤231−1时间和空间复杂度都不允许。
这类问题的直接解法就是进行“指数型”枚举搜索每个礼物选还是不选时间复杂度为 O ( 2 N ) O(2^N) O(2N)。此题 N ≤ 46 N≤46 N≤46 2 46 2^{46} 246的复杂度过高可以利用双向深搜的思想进行优化。
双向深搜
除了迭代加深之外双向深搜也可以避免在深层子树上浪费时间。
在一些题目中问题不但具有“初态”还具有明确的“终态”并且从初态开始搜索与从终态开始逆向搜索产生的搜索树都能覆盖整个状态空间。在这种情况下就可以采用双向搜索——从初态和状态出发各搜索一半产生的两棵深度减半的搜索树在中间交汇、组成最终答案。避免了层数过深时分支数量的大规模增长。
下图是直接进行一次搜索产生的搜索树 下图是双向搜索的两棵搜索树避免了避免了层数过深时分支数量的大规模增长。
算法实现
将礼物分成两部分
首先从前一半礼物中枚举出所有组合将可能达到 0 ∼ W 0\sim W 0∼W之间的所有重量值存放在一个数组 a [ ] a[] a[]中并对数组进行排序、去重然后进行第二次搜索尝试从后一半礼物中枚举出所有组合对于每个可能达到的重量 k k k在第一部分得到的数组 a [ ] a[] a[]中查找 k a [ i ] ≤ W ka[i]\le W ka[i]≤W的最大值可以使用二分查找。
这样算法的时间复杂度为 O ( 2 N 2 × l o g N 2 ) O(2^{\frac{N}{2}}\times log\frac{N}{2}) O(22N×log2N)。
代码实现
#include iostream
#include cstring
#include algorithm
using namespace std;
typedef long long LL;
const int N 50;
int w[N];
int cnt, a[1 25]; //存储前一半礼物所有组合的重量
int n, W, ans;
void dfs1(int i, int k) //k表示目前组合的重量
{if(i n / 2) //只搜索前一半的礼品{a[cnt ] k; //将组合得到的重量存到a数组return;}if((LL)k w[i] W) dfs1(i 1, k w[i]); //装得下第i件礼物dfs1(i 1, k); //不装第i件礼物
}
void dfs2(int i, int k)
{if(i n) //搜索完成二分查找不超过W的最大组合重量{int L 0, R cnt - 1;while(L R){int mid (L R 1) / 2;if((LL)k a[mid] W) L mid;else R mid - 1;}ans max(ans, k a[L]);return;}if((LL)k w[i] W) dfs2(i 1, k w[i]); //装得下第i件礼物dfs2(i 1, k); //不装第i件礼物
}
int main()
{cin W n;for(int i 0; i n; i ) cin w[i];//优化搜索顺序优先搜索重量较大的礼品sort(w, w n);reverse(w, w n);dfs1(0, 0); //枚举前一半礼品的组合将其组合得到的重量存到a数组sort(a, a cnt); //对前一半礼物组合得到的重量排序去重cnt unique(a, a cnt) - a;//对后一半礼物进行搜索dfs2(n / 2, 0);cout ans;return 0;
}
