题目描述

应该不是最优解，bins还是不断申请新空间(update: 不用shrink_to_fit的话不需要申请新空间)，可能有更好解决方案。甚至一边做2进制压缩一边进行dp

C++ 代码

#include <cstdio>
#include <vector> 

using namespace std;
int n, m, cap, price, num;
vector<pair<int, int>> bins; 
vector<int> dp;


int main()
{
    scanf("%d %d", &n, &m);
    dp = vector<int> (m+1);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d", &cap, &price, &num);

        // 二进制优化
        for(int j=1; j<num; num -= j, j<<=1) bins.push_back({j*price, j*cap});
        if(num) bins.push_back({num*price, num*cap});

        // 0-1背包的优化方法
        for (auto [price, v] : bins)
            for(int j=m; j>=v; j--)
                dp[j]=max(dp[j],dp[j-v]+price);

        bins.clear();
    }


    printf("%d", dp[m]);
}