当前位置:网站首页>POJ 2392 Space Elevator
POJ 2392 Space Elevator
2022-07-07 19:09:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
Multiple knapsack problem .
My backpack training question 3 , Multiple backpack .
It seems that I understand multiple backpacks a little .
My understanding of backpack nine is about multiple backpacks :
When something Volume * Number When it exceeds the capacity of the backpack , This makes a complete backpack ( Equivalent to infinite access )
void completepack(int h,int cost,int a)
{
for(int i=cost;i<=a;i++)
dp[i]=max(dp[i],dp[i-cost]+h);
}
When there are more than one item but it can't fill the backpack , Do it one by one 01 knapsack Too wasteful . Then take the binary method , Every time I take 2.
Multiply every time 2 Of Do it once 01 knapsack .
In this way, the time complexity is reduced .
void zeroonepack(int h,int cost,int a)
{
for(int i=a;i>=cost;i--)
dp[i]=max(dp[i],dp[i-cost]+h);
}
Separate like this and then decompose . Making multiple backpacks easy .
void multiplepack(int h,int cost,int c,int a)
{
if(cost*c>=a)
{
completepack(h,cost,a);
return;
// It's equivalent to making a complete backpack
}
int k=1;
while(k<c)
{
zeroonepack(h*k,cost*k,a);
c-=k;
k*=2;
// many times 01 knapsack
}
zeroonepack(h*c,cost*c,a);
}
AC Code :
#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);
}
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116608.html Link to the original text :https://javaforall.cn
边栏推荐
- 学习open62541 --- [67] 添加自定义Enum并显示名字
- Three forms of multimedia technology commonly used in enterprise exhibition hall design
- Complete e-commerce system
- 单臂路由和三层交换的简单配置
- cmd命令进入MySQL时报服务名或者命令错误(傻瓜式教学)
- The top of slashdata developer tool is up to you!!!
- 企业MES制造执行系统的分类与应用
- Will low code help enterprises' digital transformation make programmers unemployed?
- String type, constant type and container type of go language
- 脑洞从何而来?加州大学最新研究:有创造力的人神经连接会「抄近道」
猜你喜欢
[paper sharing] where's crypto?
ES6笔记一
【软件测试】从企业版BOSS直聘,看求职简历,你没被面上是有原因的
Basic operation of chain binary tree (implemented in C language)
学习open62541 --- [67] 添加自定义Enum并显示名字
Redis集群与扩展
Will low code help enterprises' digital transformation make programmers unemployed?
Charles+drony的APP抓包
Short selling, overprinting and stock keeping, Oriental selection actually sold 2.66 million books in Tiktok in one month
Continuous test (CT) practical experience sharing
随机推荐
PTA 1101 B是A的多少倍
Redis
Redis的发布与订阅
SQLite SQL exception near "with": syntax error
清华、剑桥、UIC联合推出首个中文事实核查数据集:基于证据、涵盖医疗社会等多个领域
"Decryption" Huawei machine vision Corps: Huawei is moving up and the industry is moving forward
我感觉被骗了,微信内测 “大小号” 功能,同一手机号可注册两个微信
Skills of embedded C language program debugging and macro use
Nat address translation
In 2021, the national average salary was released. Have you reached the standard?
伺服力矩控制模式下的力矩目标值(fTorque)计算
Hutool - lightweight DB operation solution
[tpm2.0 principle and Application guide] Chapter 16, 17 and 18
cmd命令进入MySQL时报服务名或者命令错误(傻瓜式教学)
SD_ DATA_ SEND_ SHIFT_ REGISTER
The top of slashdata developer tool is up to you!!!
Antisamy: a solution against XSS attack tutorial
POJ 2392 Space Elevator
Thread pool and singleton mode and file operation
Mathematical analysis_ Notes_ Chapter 11: Fourier series