[DP] 简单的烦恼

---

此题是一个有条件限制的01背包

解法1：

首先 最大体积肯定是   

其次 易得大于体积 t 的状态只能由小于 t 的状态转移而来

解法2：

最大答案肯定是 t 体积以内的最大非 t 体积 + max val[i] 

所以对物品排序， 用t体积背前n - 1个物品， 然后加上max val[i]

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    //freopen("D://test.in", "r", stdin);
    //freopen("D://test.out", "w", stdout);
 
    int T;
 
    cin >> T;
 
    while(T--)
    {
        int n, s, maxval = 0, ans = 0;
 
        cin >> n >> s;
 
        for(int i = 0; i < n; ++i)
            cin >> val[i], maxval = max(val[i], maxval);
             
 
        memset(dp, 0, sizeof(dp[0]) * (s + maxval + 100));
     
        for(int i = 0; i < n; i++)
        {
            for(int j = s + maxval; j >= val[i]; j--)
            {
                if(j - dp[j] < s || dp[j] == 0 && j - val[i] < s)
                    dp[j] = max(dp[j], dp[j - val[i]] + val[i]);
 
                ans = max(ans, dp[j]);
            }
        }
         
        cout << ans << '
';
    }
     
    return 0;
}