poj2392 Space Elevator（多重背包转化为完全背包与01背包）

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct node{
int a,b,c;
}a[430];
int dp[40500];
bool cmp(node a,node b){
return a.b<b.b;
}
int main(){
int k;cin>>k;
for(int i=1;i<=k;i++){
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
}
sort(a+1,a+1+k,cmp);
for(int i=1;i<=k;i++){
if(a[i].b>a[i].c*a[i].a){
for(int n=1;n<a[i].c;n*=2){
for(int v=a[i].b;v>=a[i].a*n;v--){
dp[v]=max(dp[v],dp[v-a[i].a*n]+a[i].a*n);
}
a[i].c-=n;
}
if(a[i].c>0){
for(int v=a[i].b;v>=a[i].a*a[i].c;v--)
dp[v]=max(dp[v],dp[v-a[i].a*a[i].c]+a[i].a*a[i].c);
}
}
else{
for(int v=a[i].a;v<=a[i].b;v++){
dp[v]=max(dp[v],dp[v-a[i].a]+a[i].a);
}
}
}
int ans=0;
for(int i=1;i<=a[k].b;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
}

最后

以上就是爱撒娇超短裙为你收集整理的poj2392 Space Elevator（多重背包转化为完全背包与01背包）的全部内容，希望文章能够帮你解决poj2392 Space Elevator（多重背包转化为完全背包与01背包）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。