当前位置:网站首页>POJ 2392 Space Elevator
POJ 2392 Space Elevator
2022-07-07 16:54:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
多重背包问题。
我的背包训练第三题,多重背包。
似乎有点理解多重背包了。
我对背包九讲多重背包的理解:
当某件物品 体积*数量 超过背包的容积的时候,这就做全然背包(相当于无限取)
void completepack(int h,int cost,int a)
{
for(int i=cost;i<=a;i++)
dp[i]=max(dp[i],dp[i-cost]+h);
}
而某件物品有多件却不能装满背包的时候,一件一件的来做01背包 太浪费。然后採取二进制的办法,每次乘2。
把每次乘2 的 来做一次01 背包。
这样时间复杂度减少 。
void zeroonepack(int h,int cost,int a)
{
for(int i=a;i>=cost;i--)
dp[i]=max(dp[i],dp[i-cost]+h);
}
这样分开然后再分解。让多重背包就简单起来了。
void multiplepack(int h,int cost,int c,int a)
{
if(cost*c>=a)
{
completepack(h,cost,a);
return;
//相当于做一次全然背包
}
int k=1;
while(k<c)
{
zeroonepack(h*k,cost*k,a);
c-=k;
k*=2;
//多次01背包
}
zeroonepack(h*c,cost*c,a);
}
AC 代码:
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int dp[40001];
int n;
struct lx
{
int h,c,a;
}l[401];
bool cmp(lx a,lx b)
{
return a.a<b.a;
}
void zeroonepack(int h,int cost,int a)
{
for(int i=a;i>=cost;i--)
dp[i]=max(dp[i],dp[i-cost]+h);
}
void completepack(int h,int cost,int a)
{
for(int i=cost;i<=a;i++)
dp[i]=max(dp[i],dp[i-cost]+h);
}
void multiplepack(int h,int cost,int c,int a)
{
if(cost*c>=a)
{
completepack(h,cost,a);
return;
}
int k=1;
while(k<c)
{
zeroonepack(h*k,cost*k,a);
c-=k;
k*=2;
}
zeroonepack(h*c,cost*c,a);
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
int m=0;
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&l[i].h,&l[i].a,&l[i].c);
m=max(m,l[i].a);
}
memset(dp,0,sizeof(dp));
sort(l,l+n,cmp);
for(int i=0;i<n;i++)
{
multiplepack(l[i].h,l[i].h,l[i].c,l[i].a);
}
int ans=0;
for(int i=0;i<=m;i++)
//printf("%d =\n",dp[i]);
ans=max(ans,dp[i]);
printf("%d\n",ans);
}
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116608.html原文链接:https://javaforall.cn
边栏推荐
- C语言中匿名的最高境界
- Datasimba launched wechat applet, and datanuza accepted the test of the whole scene| StartDT Hackathon
- Cadre de validation des données Apache bval réutilisé
- Will domestic software testing be biased
- A few simple steps to teach you how to see the K-line diagram
- How to choose the appropriate automated testing tools?
- 3.关于cookie
- unity2d的Rigidbody2D的MovePosition函数移动时人物或屏幕抖动问题解决
- 低代码助力企业数字化转型会让程序员失业?
- 云安全日报220707:思科Expressway系列和网真视频通信服务器发现远程攻击漏洞,需要尽快升级
猜你喜欢
Redis cluster and expansion
CVPR 2022 - learning non target knowledge for semantic segmentation of small samples
Will low code help enterprises' digital transformation make programmers unemployed?
Cadre de validation des données Apache bval réutilisé
Static routing configuration
Tsinghua, Cambridge and UIC jointly launched the first Chinese fact verification data set: evidence-based, covering many fields such as medical society
Comparison and selection of kubernetes Devops CD Tools
DeSci:去中心化科学是Web3.0的新趋势?
Redis
Simple configuration of single arm routing and layer 3 switching
随机推荐
Rules for filling in volunteers for college entrance examination
强化学习-学习笔记8 | Q-learning
静态路由配置
Redis的发布与订阅
數據驗證框架 Apache BVal 再使用
socket編程之常用api介紹與socket、select、poll、epoll高並發服務器模型代碼實現
面试唯品会实习测试岗、抖音实习测试岗【真实投稿】
嵌入式C语言程序调试和宏使用的技巧
Five network IO models
DeSci:去中心化科学是Web3.0的新趋势?
回归问题的评价指标和重要知识点总结
pip相关命令
【剑指 Offer】59 - I. 滑动窗口的最大值
Learn open62541 -- [67] add custom enum and display name
Kubernetes DevOps CD工具对比选型
3. About cookies
Redis
Some key points in the analysis of spot Silver
Save the memory of the model! Meta & UC Berkeley proposed memvit. The modeling time support is 30 times longer than the existing model, and the calculation amount is only increased by 4.5%
你真的理解粘包与半包吗?3分钟搞懂它