题解 | 【模板】完全背包_二进制拆分写法

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m, c = 0;
        cin >> n >> m;
        vector<int> dp(m + 1, 0), w, v;
        for (int i = 1; i <= n; ++i) {
            int wi, vi;
            cin >> wi >> vi;
            int k = m / wi;
            int t = 1;
            while(k > 0){
                int take = min(k, t);
                w.push_back(take * wi);
                v.push_back(take * vi);
                k -= take;
                t <<= 1;
            }
        }
        for(int i = 0;i < w.size();++i){
            for(int j = m;j >= w[i];--j){
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
            }
        }
        cout << dp[m] << endl;
    }
}
// int main() {
//     int T;cin>>T;
//     while(T--){
//         int n, m;cin>>n>>m;
//         vector<int> dp(m + 1, 0);
//         for(int i = 1;i <= n;++i){
//             int w, v;cin>>w>>v;
//             for(int j = w;j <= m;++j){
//                 dp[j] = max(dp[j], dp[j-w] + v);
//             }
//         }
//         cout<<dp[m]<<endl;
//     }
// }
// 64 位输出请用 printf("%lld")