太空电梯

奶牛们要去太空了！它们打算用方块建造一座太空电梯。现在它们有 \(N\) 种方块，第 \(i\) 种方块有一个特定的高度 \(h_i\)，一定的数量 \(c_i\)。为了防止宇宙射线破坏方块，第 \(i\) 种方块的任何部分不能超过高度 \(a_i\)。
请用这些方块堆出最高的太空电梯。

每件物品最多可以\(M\)次，求总价值最大。
\(m\)代表次数，\(j\)代表背包容量，\(val\)代表当前物品的价值

第一种写法

第二层\(for\)循环不能使用正序遍历，并且每个物品的次序遍历要放在第三层for循环。假如正序遍历，当\(j=10\)时，\(m=1 val=2\)的话，那么这一次便给\(dp[j-m*val](dp[10-2]=dp[8])\)赋值，当\(m=2,val=2,j=12\)时，又会给\(dp[8]\)再赋值一次。同理假如\(m\)的循环是第二层结果也是一样，会重复赋值

  ufr(i, 1, n)
      lfr(j, dat[i].a, dat[i].h) 
        for (int k = 1;j >= k * dat[i].h && k <= dat[i].c; ++k)
          dp[j] = max(dp[j], dp[j - k * dat[i].h] + k * dat[i].h);
  f.pt(*max_element(goto(dp, dat[n].a)));

第二种写法

对同一个物品对容量为\(w\)的背包赋值\(m\)次

  ufr(i, 1, n)
    ufr(k, 1, dat[i].c)
      lfr(j, dat[i].a, dat[i].h){
         dp[j] = max(dp[j], dp[j - dat[i].h] + dat[i].h);
      }
  f.pt(*max_element(goto(dp, dat[n].a)));

本题的第二种做法

如果第\(i\)件物品堆积，那么如果要保证最大值，那么一定是在第\(i-1\)的基础之上进行堆积，将第\(dp[j-k*val]\)能赋值的位置都设置为\(true\)，那么第\(i\)件物品一定是在\(dp[j-k*val]\)基础之上操作

   ufr(i, 1, n) 
     lfr(j, dat[i - 1].a, 0) if (dp[j]) 
        for (int k = 1; k <= dat[i].c && j + k * dat[i].h <= dat[i].a; ++k)
          dp[j + k * dat[i].h] = true;
 lfr(i, dat[n].a, 0)if (dp[i]) f.pt(i).ln();

原文地址：http://www.cnblogs.com/GuanStudy/p/16916845.html