【动态规划】超时优化

Question

已解决。

```c++
#include<bits/stdc++.h>
using namespace std;

const int M=1e6+10;
int c[M*2],a[M],n,k,ans,maxn;
int s1[50],s2[50]; 

void f(int b)
{
    memset(s1,0,sizeof(s1));
    memset(s2,0,sizeof(s2));
    int len1=0,len2=0,kk=k;
    while(b)
        s1[++len1]=b%2,b/=2;
    while(kk)
        s2[++len2]=kk%2,kk/=2;
    int len=max(len1,len2);
    for (int i=1;i<=len/2;i++)
        swap(s1[i],s1[len-i+1]),swap(s2[i],s2[len-i+1]);
    int sum=0;
    for (int i=1;i<=len;i++)
        if (s2[i]==0)
            sum=sum*2+s1[i];
        else
        {
            int k1=(sum*2+s1[i])*1<<(len-i),k2=(sum*2+1+s1[i])*1<<(len-i);
            c[k1]++,c[k2]--;
            sum=sum*2+(s1[i]^1);
        }
    c[sum]++,c[sum+1]--;
}

int main()
{
    scanf("%d%d",&n,&k);maxn=k;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f(a[i]);
        maxn=max(maxn,a[i]);
    }
    for (int i=1;i<=maxn*2;i++)
        c[i]+=c[i-1];
    for (int i=0;i<=maxn*2;i++)
        ans=max(ans,c[i]);
    cout<<ans;
    return 0;
}

```

Answer 1

前言
编写不易给个采纳哦!

分析
根据题意，我们要从 $n$ 个物品中选取若干个物品，使得它们的总和为 $m$。对于第 $i$ 个物品，可以选择若干次。最终输出的结果就是所有可能方案中满足条件的方案数目之和。
在本代码中，我们定义了一个二维数组 $f[i][j]$ ，表示前 $i$ 个物品中选取若干个物品，使得它们的总和为 $j$ 的方案数目。
我们可以使用三重循环来填写这个数组。具体来说，外层循环枚举物品编号 $i$ ，中间循环枚举背包容量 $j$ ，内层循环枚举第 $i$ 个物品选取的次数 $k$ 。在每次循环中，我们根据状态转移方程 $f[i][j]=\sum_{k=0}^{\infty}f[i-1][j-k\times a[i]]$ 来更新 $f[i][j]$ 的值。其中， $a[i]$ 表示第 $i$ 个物品的价值。
但是，这种方法的时间复杂度是 $O(nm^2)$ ，当 $n$ 和 $m$ 较大时，会导致程序运行超时。
因此，可以对上述代码进行优化。一种优化方法是使用滚动数组的技巧，将二维数组 $f[i][j]$ 转化为一维数组 $f[j]$ ，这样就可以减少一个维度的循环。具体来说，我们可以将循环顺序改为：外层循环枚举物品编号 $i$ ，内层循环倒序枚举背包容量 $j$ （注意，倒序循环的原因是防止后面的状态覆盖前面的状态，从而出现重复统计）。在循环每个内层循环时，我们根据状态转移方程 $f[j]=\sum_{k=0}^{\infty}f[j-k\times a[i]]$ 来更新 $f[j]$ 的值。
此外，对于循环内的第三重循环，也可以进行优化。具体来说，我们可以根据当前物品的价值 $a[i]$ 来计算出最多可以选取多少个该物品，然后只需循环这些次数即可，而不需要循环所有非负整数。

效果截图

源码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5001;
const int mod = 1000000000;
int f[maxn],a[maxn];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        a[i] = i;
    }
    f[0] = 1; // 边界条件
    for(int i = 1;i <= n;i++){
        int limit = m / a[i]; // 计算最多可以选取多少个物品 i
        for(int k = 1;k <= limit;k++){ // 只需循环这些次数
            for(int j = m;j >= k * a[i];j--){ // 倒序循环
                f[j] = (f[j] + f[j-k*a[i]]) % mod; // 状态转移方程
            }
        }
    }
    cout << f[m] << endl; // 输出结果
    return 0;
}