0-1背包问题-动态规划

0-1背包问题-动态规划

一、问题描述

给定n种物品和一个背包。物品i 的重量是 w_i ，其价值是v_i ，背包的容量为c 。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

0-1背包问题

在选择装入背包中物品时，对每种物品 i 只有两种选择：装入 、 不装入 。 即不能将物品 i 多次装入背包，也不能只装物品 i 的一部分。

背包问题

在选择装入背包中的物品时，对每种物品 i 只有三种选择：装入、不装入、部分装入。

二、数学模型描述

$$给定c > 0， w_i > 0， v_i > 0 (1≤ i ≤n)，要求找出一个 n 元 0-1 向量 (x_1, x_2, ⋯ , x_n) , x_i ∈{0,1} (1≤ i ≤n)，使得\sum^n_{i=1} w_ix_i \leq c,而且 \sum^n_{i=1}v_ix_i \ 达到最大。$$

三、最优子结构性质

四、逻辑递推式

五、代码

/**
0-1 背包问题
v 价值数组
w 体积数组
c 背包容量
n 物品数量
m 价值-容量数组
**/
void Knapsack(int v[], int w[], int c ,int n , int **m){
    //i 遍历 n 个物品
    for(int i = 1 ; i <= n ; i ++ ){
        // j 遍历 c 的容量
        for(int j = 0 ; j <= C ; j ++ ){
            // 第一种情况：当前容量不足以存放第 i 个容量
            m[i][j] = m[i-1][j] ;
            // 第二种情况：当前容量足以存放第 i 个容量
            if( j >= w[i] ){
                //在 1.将其放入后，m[i-1][j-wi]+v[i]值
               	//	 2.不将其放入，m[i-1][j]值
                // 两种情况取最大值，放入 m[i][j]
                m[i][j] = max(m[i-1][j-w[i]] + v[i] , m[i-1][j] );
            }
            
        }
    }
    return m[n][c] ;
}

/**
路径函数
用于追踪最优解的输出路径
**/
void Trace(int v[], int w[], int c, int n , int **m){
    
}