口袋可以装下体积总和为 m 的宝石。 一共有 n+1 种不同的宝石。第 i (1≤i≤n) 种宝石一共有 ai 颗，每一颗的体积都是 bi（保证 bi=2x，其中 x 是一个正整数，2x 表示 x 个 2 的乘积，比如说 24=2×2×2×2）。第 n+1 种宝石有无限多颗，每一颗的体积都是 1。 现在蜗蜗想用数量最少的宝石装满口袋，请求出蜗蜗最少要使用多少颗宝石。 输入格式 第一行一个正整数 test 表示数据组数。 对于每组数据，第一行两个整数 n,m。接下来 n 行，每行两个整数 ai,bi 分别表示一种宝石的数量和体积。 输出格式 对于每组数据，输出一行一个整数，表示蜗蜗最少要使用多少颗宝石。 样例输入 2 2 7 1 2 1 4 2 6 1 2 1 4 样例输出 3 2 数据规模 对于 30% 的数据，保证所有的 ai=1。 对于 100% 的数据，保证 1≤test≤105,1≤n≤31,0≤m<231,1≤ai<231,2≤bi<231，bi 已经从小到大排好序了并且两两不同。 c++不用vector

首先，我们可以将问题转化为一个背包问题来求解。

我们定义一个二维数组 dp，其中 dp[i][j] 表示使用前 i 种宝石装满体积为 j 的口袋所需的最少宝石数量。

对于 dp[i][j]，我们有两种选择：

1. 不使用第 i 种宝石，那么 dp[i][j] = dp[i-1][j]；
2. 使用第 i 种宝石，那么 dp[i][j] = dp[i-1][j - a[i]*b[i]] + a[i]，其中 a[i] 是第 i 种宝石的数量，b[i] 是第 i 种宝石的体积。

我们只需选择上述两种情况中的最小值即可。

根据以上思路，我们可以编写如下的 C++ 代码来解决这个问题：

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

const int MAXN = 35;
const int MAXM = 1000005;

int n, m;
int a[MAXN], b[MAXN];
int dp[MAXN][MAXM];

int main() {
    int test;
    cin >> test;
    while (test--) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i] >> b[i];
        }
        
        memset(dp, 0x3f, sizeof(dp)); // 初始化 dp 为一个较大的数，表示无穷大
        
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                dp[i][j] = dp[i-1][j];
                if (j >= a[i]*b[i]) {
                    dp[i][j] = min(dp[i][j], dp[i-1][j - a[i]*b[i]] + a[i]);
                }
            }
        }
        
        cout << dp[n][m] << endl;
    }
    
    return 0;
}

上述代码使用了动态规划的思想，时间复杂度为 O(n*m)，其中 n 是宝石的种类数，m 是口袋的体积。