【贪心+01背包】Tower

男娘i 2024-03-22 23:50 79阅读 0赞

这是个很经典的问题

[Tower - 洛谷][Tower -]

题意：

![e16534c6f0fc438c8ec6825fafa78ed9.png][]

思路：

首先可以确定是个背包而且肯定要排序，但是根据什么排序不确定

因为交换相邻两个箱子只有对自身产生影响，所以可以贪心地考虑这两个箱子如何摆最优，而又因为本身上面的总重量不变，所以只用考虑这两个箱子的限制：一上一下的x,y，x 在上面还可放 sy−wx，y 在上可放 sx−wy，显然若 sy−wx>sx−wy 则 x 在上，否则 y 在上，移项一下得 sy+wy>sx+wx 则 x 在上，于是按 s+w 升序排序，然后每次都把箱子放在最下方即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e3+10;
    const int mxe=1e5+10;
    const int mxv=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    struct ty{
        int w,s,v;
    }p[mxn];
    
    int N;
    int w[mxn],s[mxn],v[mxn];
    int dp[mxv];
    
    bool cmp(ty x,ty y){
        return x.s+x.w<y.s+y.w;
    }
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++){
            cin>>p[i].w>>p[i].s>>p[i].v;
        }
        sort(p+1,p+1+N,cmp);
        int ans=0;
        for(int i=1;i<=N;i++){
            for(int j=p[i].w+p[i].s;j>=p[i].w;j--){
                dp[j]=max(dp[j],dp[j-p[i].w]+p[i].v);
                ans=max(ans,dp[j]);
            }
        }
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[Tower -]: https://www.luogu.com.cn/problem/AT_dp_x
[e16534c6f0fc438c8ec6825fafa78ed9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8b2eea90a3df49b8a3f0ac79e78cc009.png

发表评论取消回复

表情：

评论列表（有 0 条评论，79人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心+01背包】Tower

这是个很经典的问题 [Tower - 洛谷][Tower -] 题意： ![e16534c6f0fc438c8ec6825fafa78ed9.png][] 思路：首

男娘i/ 2024年03月22日 23:50/ 0 赞/ 80 阅读

相关贪心-01

贪心算法贪心算法：只顾眼前的苟且。即在对问题求解时，总是做出在当前看来是最好的选择其实不懂什么是贪心，为什么那样就是最优解最优装载问题——加勒比海盗货物

超、凢脫俗/ 2023年07月12日 05:26/ 0 赞/ 1 阅读

相关背包问题多种贪心_面试高频算法系列 | 第1话-01背包

![6899b34c2c2ac54398b3facae49748e8.png][] PART1 楔子由于01背包的问题属于经典问题。很多文章会直接将经典的解题思路写出

喜欢ヅ旅行/ 2023年01月07日 15:27/ 0 赞/ 169 阅读

相关 01背包

01背包题目描述给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个输入的第一行包

爱被打了一巴掌/ 2022年12月04日 04:27/ 0 赞/ 178 阅读

相关背包问题-背包01-苹果

package 动态规划.背包01; import java.util.Scanner; public class 苹果 \{ static class

野性酷女/ 2022年07月12日 12:12/ 0 赞/ 259 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 248 阅读

相关 01背包

> 题目：有一个背包，体积为m，现在给你n个石头，每个石头都有价值和体积，问这个背包可以装下多大价值的石头。 > > 输入： > 第一行两个整数n，m，分别代表石头的个数

╰半夏微凉°/ 2022年06月08日 09:37/ 0 赞/ 211 阅读

相关 01背包

01背包 > 且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ > > 小Ho现在手上有M张奖券，而奖品区有N

水深无声/ 2022年05月31日 06:29/ 0 赞/ 650 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 369 阅读

相关背包问题-01背包，完全背包，多重背包

背包问题-01背包，完全背包，多重背包 -------------------- 01背包：概念：有Goods\_Num件物品，MAX\_V

太过爱你忘了你带给我的痛/ 2022年05月14日 09:23/ 0 赞/ 305 阅读