送礼物题解

标签：cnt 达达 力气 题解 ans 样例 送礼物 dp

题目描述

达达帮翰翰给女生送礼物，翰翰一共准备了N个礼物，其中第i个礼物的重量是G[i]。

达达的力气很大，他一次可以搬动重量之和不超过W的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

---

输入格式

第一行两个整数，分别代表W和N。

以后N行，每行一个正整数表示G[i]。

---

 

 输出格式

仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。

---

 

样例

样例输入

复制20 5
7
5
4
18
1

样例输出

复制19

数据范围与提示

1≤N≤48, 1≤W,G[i]≤231−1

 

---

 

分析

对于初学时的我来说，我当然不知道这道题该怎么做

听了老师的讲解后，我大约知道了怎么做：

首先观察数据范围，一个物品只有选择和不选择两个方法，所以用暴力搜索的话，时间复杂度是2的48次方，不可行。

但是2的24次方，似乎可行。

于是我们可以想到双向搜索，定义一个中点，从开头往中点搜索w的值，并用dp数组存储

再从中间往后面搜，搜到一个值，就在dp数组里面找到小于等于总的力气 - 当前已用的力气的值，然后相加和ans比较大小

dp数组需要排序才能二分

dp数组去重可以降低时间复杂度

中点的定义是一门玄学，运气好的话，定义的点可以降低运行时间

还有一个优化

重量需要从大到小排序，这个细节我并不是很理解。

听了同学的讲解后，我发现有很多地方可以优化，直接跳过，比如手写upper_bound以及。。。（请各位移步其他博客）

---

 

#include <bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 50 ;
ll n, a[MAXN], w, ans = 0, dp[(1 << 24) + 4], cnt = 0, m ;//m是折半的分界点 
void dfs1(ll sum, ll id){//从大到小排序 
    if(id == m){
        dp[cnt ++] = sum ;
        return ;
    }
    dfs1(sum, id + 1) ;
    if(sum + a[id] <= w)    dfs1(sum + a[id], id + 1) ;
    return ;
}
void Find(ll sum)
{
    ll x = w - sum ;
    ll res ;
    res = upper_bound(dp, dp + cnt, x) - dp ;
    if(res == 0){
        ans = max(ans, sum) ;
    }else{
        ans = max(ans, dp[res - 1] + sum) ;
    }
    return ;
}
void dfs2(ll sum, ll id)
{
    if(id == n){
        Find(sum) ;
        return ;
    }
    dfs2(sum, id + 1) ;
    if(sum + a[id] <= w){
        dfs2(sum + a[id], id + 1) ;
    }
    return ;
} 
int main(){
    scanf("%lld%lld", &w, &n) ;
    for(ll i = 0; i < n; i ++) scanf("%d", &a[i]) ;
    sort(a + 0, a + n, greater<int>()) ;
    m = n / 2 + 1;
    dfs1(0, 0) ;
    sort(dp, dp + cnt) ;
    cnt = unique(dp, dp + cnt) - dp ; 
    dfs2(0, m) ;
    printf("%lld", ans) ;
    return 0 ;
} 

 

---

 

这道题目自己目前还有疑点。Thinking...

标签：cnt,达达,力气,题解,ans,样例,送礼物,dp
From： https://www.cnblogs.com/ybC202444/p/17057520.html