algorithm - 如何改进这个动态规划解决方案(算法优化)

Question

问题陈述:

Assurance Company of Moving (ACM) 是一家为人们搬家的公司。最近，一些学校想把他们的电脑搬到另一个地方。所以他们请求 ACM 帮助他们。一所学校预留了K辆卡车搬家，它有N台电脑要搬家。为了不浪费卡车，学校要求ACM使用所有的卡车。也就是说，每辆货车里肯定有一些电脑，不能有空货车。 ACM 想知道用 K 辆卡车移动 N 台计算机时存在多少个分区 shemes，ACM 要求您计算给定 N 和 K 的不同 shemes 的数量。您不必关心顺序。例如N=7,K=3，下面3个partition instance被认为是同一个，应该算作一个sheme:"1 1 5","1 5 1","5 1 1"。每辆卡车可以装载几乎无限的电脑!!

节省时间:

你必须计算有多少个序列 a[1..k] 存在:

1) a[i] + a[2] + .... + a[k] = N 使得排列无关紧要

我的 O(N*K^2) 解决方案(不知道如何改进它)

#include<assert.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int DP[5001][5001];
void ini()
{
    int i,j,k;
    DP[0][0]=1;
    for(k=1;k<=500;k++)
        for(j=1;j<=500;j++)
           for(i=1;i<=500;i++)
            {
                DP[i][j]+=j>=k?DP[i-1][j-k]:0;
                DP[i][j]%=1988;
            }
    return ;
}
int main()
{
    ini();
    int N,K,i,j;
    while(1)
    {
        scanf("%d%d",&N,&K);
        if(N==0 && K==0)
            return 0;
        int i;
        if(DP[K][N]==0)
        {assert(0);}
        printf("%d\n",DP[K][N]);
    }
    return 0;
}

我的解决方案的解释 DP[i][j] 表示我可以只使用 i 辆卡车拥有 j 台计算机的方法数。 k 代表我正在处理的计算机数量，这意味着我只是在避免排列!

如何将其改进为 O(N*K)？

问题约束

N (1<=N<=5000) and K(1<=K<=N)

问题链接:Problem Spoj

Answer 1

就说你有K个礼盒和N个巧克力。

我将从递归和真正容易将其转换为迭代解决方案开始。

避免重复的关键是按升序分配巧克力(降序也可以)。所以你 7 block 巧克力，我在第一个盒子里放 2 block 巧克力，我会在第二个盒子里至少放 2。为什么？这有助于避免重复。

         now onwards TCL = totalChocholatesLeft & TBL  = totalBinsLeft

         So S(TCL,TBL) =  S(TCL-TBL,TBL) + S(TCL,TBL-1);

         you have to call the above expression starting with S(n-k), k)

         Why? because all boxes need at least one item so first put `1` each box. 
         Now you are left with only `n-k` chocolates.

就是这样!这就是 DP 递归。

它是如何工作的？

        So in order to remove repetitions we are maintaning the ascending order.
        What is the easiest way to maintain the ascending order ? 

如果你在第 i 个盒子里放 1 block 巧克力，那么在它前面的所有盒子里都放 1 block i+1, i++2 .....k。 因此，将巧克力放入礼品盒后，您有两种选择:

要么你想继续当前框:

                S(TCL-TBL,TBL) covers this

或者移动下一个框只是不再考虑这个框

                S(TCL,TBL-1) covers this.

等价的 DP 会产生 TC : O(NK)