『动态规划·背包』Gift

题目描述

题解

如果当前的第$i$个物品不选，且在不选的物品中是最小的，那么这就意味这体积小于$a_i$时不会再有其它物品填充背包，那么对于其它的物品进行完01背包后所贡献的答案是:$$\sum _{i=m?a_i+1}^{m}f[i]$$.

但是这么做有两个难点：时间复杂度不够优秀，且无法保证当前物品是否是没有选则的物品中最小的。

因此我们在枚举某一个点是否是最小的时候，强制让这一个点不选，比它小的都选，比它大的看情况挑。

我们来思考使用用$O(n^2)$级别的算法来实现。显然，答案分成两部分：

• 比这个点体积大的做01背包。
• 比这个点体积小的强制选。

此时我们需要排序，从大到小，不要将状态的第一维省略，我们就可以得到某一部分的较大体积的01背包结果。

很简单，转移方程是：$$f[i][j]=f[i?1][j]+f[i?1][j?a[i]]$$

再强制选取某一个物品，根据较大物品形成的01背包状态进行强制转移，另$S={\sum }_{j=i+1}^m{a}_j$.

可以这么转移,设$g[i]$表示强制选取第$i+1$件以后的物品的方案：$$g[j]=f[i?1][j?S]$$

然后答案就是：$$ans=\sum _{i=1}^n\sum _{j=m?a+i+1}^m{g}_j$$

代码如下：

#include <bits/stdc++.h>#define int long longusing namespace std;
const int N = 2000;
const int P = 1000000007;int n, m, ans = 0;
int a[N], f[N][N], s[N];signed main(void)
{
    cin>>n>>m;for (int i=1;i<=n;++i) cin>>a[i];sort(a+1,a+n+1);reverse(a+1,a+n+1);//从大到小排序 f[0][0] = 1;for (int i=1;i<=n;++i)for (int j=0;j<=m;++j){
    if (j >= a[i]) f[i][j] = (f[i-1][j]+f[i-1][j-a[i]]) % P;//01背包 else f[i][j] = f[i-1][j];}for (int i=n;i>=1;--i) s[i] = s[i+1]+a[i];//后缀和 for (int i=1;i<=n;++i){
    //枚举强制不选择的物品//强制选择i+1-n的物品int v = s[i+1];int g[10000] = {
    };for (int j=m;j>=v;--j) g[j] = f[i-1][j-v];for (int j=m-a[i]+1;j<=m;++j) ans = (ans+g[j]) % P;}cout<<ans<<endl;return 0;
}

总结：

这到题难就难在如何想到答案总计要和一通最小值相关，然后再各种优化乱搞即可。