完全背包问题入门（dp）

问题描述：

有n种重量和价值分别为Wi,Vi的物品，从这些中挑选出总重量不超过W的物品，求出挑选物品的价值总和的最大值，每种物品可以挑选任意多件。

分析：

令dp[i+1][j]表示从前i件物品中挑选总重量不超过j时总价值的最大值。则递推关系为：

dp[0][j]=0;

dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-kw[i]]+kv[i]);

核心代码可以表示为：

int dp[100][100];

void solve()

{

    for(int i=0;i<n;i++)

        for(int j=0;j<W;j++)

        for(int k=0;k*w[i]<=j;k++)

        dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);

}

这是一个三重的for循环，我们可以通过变形将上面的一重k循环去掉，那么上面的程序就变为：

int dp[100][100];

void solve()

{

    for(int i=0; i<n; i++)

        for(int j=0; j<W; j++)

        {

            if(j<w[i])

                dp[i+1][j]=dp[i][j];

            else

                dp[i+1][j]=max(dp[i][j],dp[i+1][j-w[i]]+v[i]);

        }

}

此外，01背包和完全背包问题都可以转化为一维的问题来实现，

01背包的情况：

int dp[100];

void solve()

{

    for(int i=0; i<n; i++)

        for(int j=W; j>=w[i]; j--)

        {

            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

        }

}

完全背包的情况：

int dp[100];

void solve()

{

    for(int i=0; i<n; i++)

        for(int j=w[i];j<=W;j++)

        {

            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

        }

}

巴特西

完全背包问题入门（dp）

最新文章

热门文章

巴特西

完全背包问题入门 （dp）

最新文章

热门文章

完全背包问题入门（dp）