第二节 0 1背包问题 0 1 Knapsack Problem 精通C语言 递归算法和动态规划

 第二节 0 1背包问题   0 1 Knapsack Problem

第一节 序 斐波那契数列         Fibonacci

第二节 0 1背包问题   0 1 Knapsack Problem

第三节 编辑距离         edit distance

第四节 子集总和         subset sum

第五节 钢条切割          cut rod

第六节 硬币找零          Coin Change

第七节 最长公共子序列         Longest Common Subsequence

第八节 矩阵链式乘法 Matrix Chain Multiplication

第九节 最优游戏策略 Optimal Strategy for a Game

第十节 最优二叉查找树         Optimal Binary Search Tree

第十一节 最长递增子序列 Longest Increasing Subsequence

问题描述

给定n个物品的权重(weight)和价值(value/profit)，将这些物品放在容量为W的背包中，以在背包中获得最大的总价值。注意，可以选择重量之和小于或等于背包W的物品。

问题方案

问题是要找到一些子集，以便–

1.子集中所有项目的重量总和应小于或等于背包容量

2.在满足上述条件1的所有子集中，期望的子集是其中其项的总和最大的子集。

例子:

Case-1:

数量, n = 4

 

权重, w[] = 2 3 4 5 

价值,  v[] = 3 4 5 6

 

背包容量, W = 5 

背包中获得最大的总价值 = 7 

Case-2:

n = 3

w[] = 3 2 1

v[] = 5 3 4

 

W = 5 

背包中获得最大的总价值 = 9 

Case-3:

n = 5

w[] = 1 2 3 2 2

v[] = 8 4 5 4 3

 

W = 4 

背包中获得最大的总价值 = 13

递归解决方案

考虑所有项目子集，并计算所有子集的总权重和价值。仅考虑总权重小于W的子集。从所有此类子集中，选择最大值子集。

最优子结构：要考虑项目的所有子集，每个项目可能有两种情况。

情况1：该项目包含在最佳子集中。

情况2：该项目未包含在最佳子集中。

可以从“ n”个项目获得的最大值是以下两个值中的最大值。

通过n-1个项和W权重（不包括第n个项）获得的最大值。

第n个项目的值加上n-1个项目获得的最大值，W减去第n个项目（包括第n个项目）的权重。

时间复杂度为 O(2^n).

int knapsack(int w[], int p[], int n, int W)

{

if(W == 0)

        return 0;   

     if(n==0)

         return 0; 

   

if(w[n-1] > W)

            return knapsack(w, p, n-1, W);

     return max(knapsack(w, p, n-1, W), p[n-1] + knapsack(w, p, n-1, W-w[n-1]));

}

DP解决方案

创建阶数为（n + 1）*（W + 1）的矩阵，即 knapsack[n + 1] [W + 1].

knapsack[i] [j] = 背包中物品的最大可达到价值，其中i个可用物品且背包的容量为j。

初始状态 –

knapsack[0][j]=0 for 0 <= j <= W;

knapsack[i][0]=0 for 0 <= i <= n;

按照给定的递归公式开始逐行填充矩阵–

knapsack[i][j] = knapsack[i - 1][j] , if w[i] > j

Max{knapsack[i - 1][j],  v[i]+knapsack[i - 1][j-w[i]] } , if w[i] <= j

时间复杂度为 O(n*W).

int knapsack_dp(int n, int W, int w[], int p[])

{

int i,j; 

    

    int knapsack[n+1][W+1]; 

    

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

         knapsack[0][j]=0; 

   

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

         knapsack[i][0]=0;

 

     for(i=1;i<=n;i++)

    {

         for(j=1;j<=W;j++)

         {

             if(w[i-1]<=j)            

                 knapsack[i][j]=max(knapsack[i-1][j],

p[i-1]+knapsack[i-1][j-w[i-1]]);       

                     else            

                 knapsack[i][j]=knapsack[i-1][j];            

         }

    } 

    return knapsack[n][W]; 

}