01背包枚举状态，bitset优化时间复杂度

int n,k;
    cin >> n >> k;
    bitset<100010>dp;
    dp[0] = 1;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        dp|=(dp<<x);
    }
    int ans = 0;
    for(int i=0;i<=k;i++){
        if(!dp[i]){
            ans ++;
            dp|=(dp<<i);
        }
    }
    cout << ans<< endl;

假设现在得到了 [0,s−1] 内的所有整数，如果此时新发现了一个整数 x，那么把 x 加到已得到的数字中，就得到了 [x,s+x−1]内的所有整数。

分类讨论：

• 如果 x≤s，那么合并这两个区间，我们可以得到 [0,s+x−1] 内的所有整数。

• 如果 x>s，这意味着我们无法得到 s，那么就一定要把 s 加到数组中（加一个比 s 还小的数字就没法得到更大的数，不够贪），这样就可以得到 [s,2s−1]内的所有整数，再与 [0,s−1]合并，可以得到 [0,2s−1] 内的所有整数。然后再重新考虑 x 和 s 的大小关系，继续分类讨论。

把 coins排序，从小到大考虑 x=coins[i]。按照上述分类讨论来看是否要添加数字。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] coins=new int[n];
        int t=sc.nextInt();
        for(int i=0;i<n;i++){
            coins[i]=sc.nextInt();
        }
        Arrays.sort(coins);
        int ans = 0, s = 1, i = 0;
        while (s <= t) {
            if (i < coins.length && coins[i] <= s) {
                s += coins[i];
                i++;
            } else {
                s *= 2;
                ans++;
            }
        }
        System.out.println(ans);
    }
}

从小到大排序，如果num>=a[i]-1,可以直接选择，否则贪心选择不能构成的最大金币数

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define int long long
const int mod=1e+7;
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;cin >>n>>k;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(),a.end());
    int num=0,ans=0;
    for(int i=0;i<n;i++){
        while(num+1<a[i]){
            num+=num+1;
            ans++;
        }
        num+=a[i];
    }
    while(num<k) {
			ans++;
			num+=num+1;
	}
    cout<<ans<<endl;

    return 0;
 }