最优装载问题（DP）

填半年前的坑

PART I - 前言

最近在看01背包问题的时候忽然想到了这题，发现这题其实就是01背包的变形呀！
回想当年自己怎么那么无知，竟然有穷举法做这道题T^T
不得不说这半年内的进步真的是潜移默化的
三更半夜改了N次成功通过505个随机测试数据 + 2个特例，有bug再说！

PART II - 题目

题目来源
BJC
题目描述
N个集装箱要装上1艘载重量为c的轮船，其中第i个集装箱的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。可以使用贪心算法、穷举法等。
输入
第一行输入N和C，表示集装箱数量和轮船的载重，第二行输入N个集装箱的重量。
输出
约定长为N的01字符串(1:表示装)以字典序最大的那个为符合要求的装载方案。
样例输入

3 50
40 10 40
样例输出

110

PART III - 思路 + 代码

思路
将每个物品的主要价值看作1, 体积为所给的重量，这样就可以满足题意中的尽可能多
将每个物品的次要价值看作2^i，i是他们的所在位，用二进制思想来满足题意中的字典序最大
这样当dp到主要价值相同时，就更新所对应的次要价值的最大值，最后将dp[n]对应的次要价值转为二进制输出就是答案了

  #include <cstdio>
  #include <algorithm>
  #include <cstring>
  #include <iostream>
  using namespace std;
  const int N = 30;
  const int M = 10005;

  int f[M], g[M], w[N];
  char str[N];

  int main(){
      int n, v;
      while(~scanf("%d%d", &n, &v)){
          memset(f, 0, sizeof(f));
          memset(g, 0, sizeof(g));
          memset(str, '0', sizeof(str));
          for(int i = 1; i <= n; i++){
              scanf("%d", &w[i]);
          }
          for(int i = 1; i <= n; i++){
              for(int j = v; j >= w[i]; j--){
                  if(f[j] < f[j - w[i]] + 1){
                      f[j] = f[j - w[i]] + 1;   //每个物体价值为1,进行DP  
                      g[j] = g[j - w[i]] + (1 << (n - i));
                  }else if(f[j] == f[j - w[i]] + 1){
                      g[j] = max(g[j], g[j - w[i]] + (1 << (n - i)));   //f[j]相同就更新对应g[j]，使其能尽量大  
                  }
              }
          }

          int ans = g[v];   //ans就等于f[v]所对应的次要价值g[v]
          int i = n;
          str[i--] = 0;
          while(ans){   //转2进制
              str[i--] = ((ans&1) ? '1' : '0');
              ans >>= 1;
          }

          printf("%s\n", str);
      }
  }