C++ 代码

// 多重背包(二进制优化)
// O(VMS) -> O(VMlogs)
#include <iostream>
#include <vector>
using namespace std;

const int n = 1010;
int v[n], w[n], s[n];

// 状态初始化
const int m = 2010;
int f[m];

// 物品分类
struct good
{
  public:
    int v;
    int w;
    good(int vv, int ww) :v(vv), w(ww){}
};

int main()
{
  vector<good> goods;

  int N, V;
  cin >> N >> V;
  for(int i = 0; i < N; ++i)
  {
    // 物品信息输入
    cin >> v[i] >> w[i] >> s[i];

    // 物品分类(1, 2, 4, 8, ...), 建立新物品
    for(int k = 1; s[i] >= 0; s[i] -= k, k *= 2)     // 这里表达式注意顺序
    {
      goods.push_back(good(k * v[i], k * w[i]));
    }
    if(s[i] > 0)
    {
      goods.push_back(good(s[i] * v[i], s[i] * w[i]));
    }
  }

  // 转移方程(按照新物品枚举)
  for(auto good : goods)
  {
    for(int j = V; j >= good.v; --j)                 // 小优化
    {
      if(good.v <= j)
      {
        f[j] = max(f[j], f[j - good.v] + good.w);
      }
    }
  }

  cout << f[V] << endl;

  return 0;
}