POJ-动态规划-背包问题模板

背包问题模板

一、0-1背包

状态：背包容量为j时，求前i个物品所能达到最大价值，设为dp[i][j]。初始时，dp[0][j](0<=j<=V)为0，没有物品也就没有价值。

状态转移方程：由上述分析，第i个物品的体积为w,价值为v，则状态转移方程为

j<w，dp[i][j] = dp[i-1][j] //背包装不下该物品，最大价值不变
j>=w, dp[i][j] = max{ dp[i-1][j-list[i].w] + v, dp[i-1][j] } //和不放入该物品时同样达到该体积的最大价值比较

结构体：存放物品的体积和价值

struct Thing

{

    int w;

    int v;

}list[];

1.init()：dp[][]数组初始化

int s, n;//背包容量和物品总数

void init()

{

    for (int i = ; i <= s; i++) dp[][i] = ;//没有物品时最大价值均为0

}

2.package()：执行背包，求解问题

void package()

{

    for (int i = ; i <= n; i++)//循环每个物品，执行状态转移方程

    {

        for (int j = ; j <= s; j++)

        {

            if (j >= list[i].w) dp[i][j] = max(dp[i - ][j], dp[i - ][j - list[i].w] + list[i].v);

            else dp[i][j] = dp[i - ][j];

        }

    }

}

优化后的一维01背包

1.init()：dp[][]数组初始化

int s, n;//背包容量和物品总数

void init()

{

    for (int i = ; i <= s; i++) dp[i] = ;//初始化二维数组//没有物品时最大价值均为0

}

2.package()：执行背包，求解问题

void package()

{

    for (int i = ; i <= n; i++)//循环每个物品，逆序遍历j执行状态转移方程

    {

        for (int j = s; j >= list[i].w; j--)

        {

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

        }

    }

}

二、完全背包

1.init()：dp[][]数组初始化

void init()

{

    for (int i = ; i <= s; i++) dp[i] = ;//初始化二维数组//没有物品时最大价值均为0

}

2.package()：执行背包，求解问题，正序遍历即可实现复用。

void package()

{

    for (int i = ; i <= n; i++)//循环每个物品，正序遍历j执行状态转移方程

    {

        for (int j = list[i].w; j <= s; j++)

        {

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

        }

    }

}

巴特西

POJ-动态规划-背包问题模板

最新文章

热门文章