POJ 2392 -- Space Elevator 多重背包 单调队列


2392 -- Space Elevator
The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 <= h_i <= 100) and is available in quantity c_i (1 <= c_i <= 10). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i (1 <= a_i <= 40000).

Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.
Input
* Line 1: A single integer, K

* Lines 2..K+1: Each line contains three space-separated integers: h_i, a_i, and c_i. Line i+1 describes block type i.
Output
* Line 1: A single integer H, the maximum height of a tower that can be built
Sample Input
3  
7 40 3  
5 23 8  
2 52 6
Sample Output
48
Hint
OUTPUT DETAILS:

From the bottom: 3 blocks of type 2, below 3 of type 1, below 6 of type 3. Stacking 4 blocks of type 2 and 3 of type 1 is not legal, since the top of the last type 1 block would exceed height 40.
http://www.bubuko.com/infodetail-437007.html
       本题是一道多重背包问题, 不过每个物品的选择不仅仅要受该种物品的数量num[i]限制, 且该物品还受到limit[i]的限制.
这里有一个贪心的结论:
       我们每次背包选取物品时都应该优先放置当前limit[i]值最小的积木(可以画个图看看,不过不太好证明该结论). 所以我们首先把所有积木按limit[i]的值进行从小到大的排序, 然后从1编号开始选积木即可.
在进行多重背包之前要进行一次排序,将最大高度小的放在前面,只有这样才能得到最优解,如果
将大的放在前面,后面有的小的就不能取到,排序之后就可以进行多重背包了
       下面就是多重背包的过程了.
       令dp[i][j]==x表示用前i个积木且总的高度<=j时能达到的最大高度为x.
       初始化: dp全为0.
       对于每种物品, 我们要做两种选择:
       1.    num[i]*high[i]>=limit[i]时, 做一次完全背包.
       2.    Num[i]*high[i]<limit[i]时, 需要把当前物品再分类, 然后做多次01背包即可.
       最终所求: dp[n][j]的最大值. 其中j遍历[0,limit[n]]内所有数.
http://www.hankcs.com/program/cpp/poj-2392-space-elevator.html
这题要思考的方向是往多重背包这边想,高度既是“价值”又是“重量”,背包的容积是变动的a_i。性价比恒为1,优先使用a_i小的。必须按积木的a_i从小到大的顺序递推才能覆盖全部解空间,否则a_i小的积木根本码不上去。
int f[2][40000 + 16];
pair <intint> q[40000 + 16];           // 单调队列 first := 最优解 second:= 容积
 
struct Block
{
    int h, a, c;
    bool operator < (const Block & b) const
    {
        return a < b.a;
    }
};
 
Block block[400 + 16];
    for (int i = 0; i < K; ++i)
    {
        cin >> block[i].h >> block[i].a >> block[i].c;
    }
    sort(block, block + K);
 
    int cur = 0, pre = 1;
    for (int i = 0; i < K; ++i)
    {
        swap(cur, pre);
        int v, w, m;
        v = block[i].h;
        w = block[i].h;
        m = block[i].c;
        int V = block[i].a;
                    // 价值 重量 数量
        for (int mod = 0; mod < w; ++mod)
        {
            int l = 0, r = 0;     // 单调队列 首 尾
            for (int j = 0; mod + j * w <= V; ++j)
            {
                // 维持单调队列的递减特性
                while (r > l && (f[pre][mod + j * w] - j * v) > q[r - 1].first)
                {
                    // 将前面小的元素都挤出去
                    r--;
                }
                // 入队
                q[r++] = make_pair(f[pre][mod + j * w] - j * v, j);
                if (r - l > 0 && j - q[l].second > m)
                {
                    // 队列不为空,最优解对应的缺口无法填满,出队
                    l++;
                }
                f[cur][mod + j * w] = q[l].first + j * v;
            }
        }
    }
 
    cout << *max_element(f[cur], f[cur] + block[K - 1].a + 1) << endl;

http://www.cnblogs.com/kedebug/archive/2013/02/06/2908248.html
标准解法
void ZeroOnePack(int w, int val, int vol)
{
    for (int v = vol; v >= w; --v)
        dp[v] = max(dp[v], dp[v - w] + val);
}

void CompletePack(int w, int val, int vol)
{
    for (int v = w; v <= vol; ++v)
        dp[v] = max(dp[v], dp[v - w] + val);
}

void MultiplyPack(int w, int val, int num, int vol)
{
    if (w * num >= vol)
    {
        CompletePack(w, val, vol);
        return ;
    }

    int k = 1; 
    while (k <= num)
    {
        ZeroOnePack(w * k, val * k, vol);
        num -= k;
        k <<= 1;
    }
    if (num)
        ZeroOnePack(w * num, val * num, vol);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d %d %d", &type[i].h, &type[i].a, &type[i].c);

    sort(type, type + n);

    for (int i = 0; i < n; ++i)
    {
        MultiplyPack(type[i].h, type[i].h, type[i].c, type[i].a);

        for (int v = type[i].a; v <= type[n-1].a; ++v)
            dp[v] = dp[type[i].a];
    }

    printf("%d\n", dp[type[n-1].a]);
    return 0;
}

http://programming-study-notes.blogspot.com/2014/04/poj-2392-space-elevator.html
且最後要枚舉一下dp的每個値找出最大値,因為最大値不一定位在dp的最後一個位置。

struct Block{ int h;
int a;
int c;
}b[401];
bool cmp(const Block &a, const Block &b)
{
return a.a < b.a;
}
int main()
{
int K;
while (scanf("%d", &K) != EOF) {
// Input
for (int k = 0; k < K; ++k)
scanf("%d %d %d", &b[k].h, &b[k].a, &b[k].c);
sort(b, b+K, cmp);
// Knapsack
fill(dp, dp+40005, 0);
for (int k = 0; k < K; ++k)
for (int i = 0; i < b[k].c; ++i)
for (int j = b[k].a; j-b[k].h >= 0; --j)
dp[j] = max(dp[j], dp[j-b[k].h] + b[k].h);
// Ouput
int ans = 0;
for (int i = 0; i <= b[K-1].a; ++i)
ans = max(ans, dp[i]);
printf("%d\n", ans);
}
}
http://www.java3z.com/cwbwebhome/article/article17/acm847.html


public class Main{
  private int k;
  private Block block[];
  private boolean access[]=new boolean[400001];

   public Main(int k,Block block[]){
    this.k=k;
    this.block=block;
  }

  private int doIt(){
   int maxs=0;
   access[0]=true;
   Arrays.sort(block);
   for(int i=0;i< k;i++)
    {
       int t=0;
       int tmp=maxs;
       for(int j=maxs;j>=t;j--)
       {
          if(access[j])
           for(int h=1;h<=block[i].c;h++)
           {
                  int x=h*block[i].h+j;
                  if(x>block[i].a) break;
                  if(tmp< x) tmp=x;
                  access[x]=true;        
           }      
       }
       maxs=tmp;
    }
    return maxs;
   }

   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
     int k=sc.nextInt();
     Block b[]=new Block[k];
     for(int i=0;i< k;i++){
       b[i]=new Block();
       b[i].h=sc.nextInt();
       b[i].a=sc.nextInt();
       b[i].c=sc.nextInt();
     }
     Main m=new Main(k,b);
     System.out.println(m.doIt());
   }
}
class Block implements Comparable{//石头类型
  int h;//石头的高度
  int a;//最大建造高度
  int c;//这种石头的数量
   public int compareTo(Object o){ 
        Block bl = (Block)o; 
        return (int)(this.a - bl.a); 
    } 
Read full article from 2392 -- Space Elevator

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts