0-1背包问题

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci（即占用背包的空间容量），得到的价值是 Wi。
求解将哪些物品装入背包可使价值总和最大。

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

二维数组0-1背包问题的状态转移方程：
F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}

一维数组0-1背包问题的状态转移方程（优化后节省了空间）：
F[v] = max{F[v], F[v − Ci] + Wi}

分析：
1、F[i, v]
表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值
2、F[i − 1, v]
表示如果不放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入容量为 v 的背包中”
3、F[i − 1, v − Ci] + Wi
表示如果放第 i 件物品，那么问题就转化为“前 i − 1 件物品放入剩下的容量为 v − Ci 的背包中”，此时能获得的最大价值就是 F[i − 1, v − Ci] 再加上通过放入第 i 件物品获得的价值 Wi
4、
只用一个数组 F[0 . . . V ]来保证第 i 次循环结束后 F[v] 中表示的就是我们定义的状态 F[i, v] 。要求在每次主循环中我们以 v ← V . . . 0 的递减顺序计算 F[v]，这样才能保证计算 F[v] 时 F[v − Ci] 保存的是状态 F[i − 1, v − Ci] 的值

//二维数组0-1背包问题
int ZeroOnePack(vector<vector<int>>& dp, vector<int>& C, vector<int>& W, int& V)
{
    int num = C.size() - 1;//物品数量
    for (int i = 1; i <= num; i++)//i初始值为1，为了对应第一个物品
    {
        for (int v = 1; v <= V; v++)//二维数组，此时循环选择递加操作；
        {
        	if(c[i] > v) {
				dp[i][v] = dp[i-1][v];
			} else {
            	//F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}
            	dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - C[i]] + W[i]);
            }
        }
    }
    return dp[num][V];
}

int main()
{
    //数组C和W前面添加一个0，是为了方便“下标i 对应 第i个物品”
    //数组C和W存储了5个物品的数据
    vector<int> C = { 0,2,2,6,5,4 };//费用，即物品体积
    vector<int> W = { 0,6,3,5,4,6 };//价值
    int N = 5;//物品数量
    int V = 10;//背包容量
    vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0));//二维数组
    cout << "Maximum value is：" << ZeroOnePack(dp, C, W, V) << endl;
    
    return 0;
}

//一维数组0-1背包问题
int ZeroOnePack(vector<int>& dp, vector<int>& C, vector<int>& W, int& V)
{
    int num = C.size() - 1;//物品数量
    for (int i = 1; i <= num; i++)//i初始值为1，为了对应第一个物品
    {
        for (int v = V; v >= C[i]; v--)//一维数组，此时循环必须递减操作
        {
            //F[v] = max{F[v], F[v − Ci] + Wi}
            dp[v] = max(dp[v], dp[v - C[i]] + W[i]);
        }
    }
    return dp[V];
}

int main()
{
    //数组C和W前面添加一个0，是为了方便“下标i 对应 第i个物品”
    //数组C和W存储了5个物品的数据
    vector<int> C = { 0,2,2,6,5,4 };//费用，即物品体积
    vector<int> W = { 0,6,3,5,4,6 };//价值
    int N = 5;//物品数量
    int V = 10;//背包容量
    vector<int> dp(V + 1, 0);//一维数组
    cout << "Maximum value is：" << ZeroOnePack(dp, C, W, V) << endl;
    
    return 0;
}

完全背包问题

有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。放入第 i 种物品的费用是 Ci，价值是 Wi。
求解：将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。

不同于0-1背包问题：每种物品有无限件。

二维数组完全背包问题的状态转移方程：
F[i, v] = max{F[i − 1, v − kCi] + kWi | 0 ≤ kCi ≤ v}

分析：
1、F[i, v]
表示前 i 种物品放入一个容量为 v的背包的最大价值
2、
当 k=0 时，状态转移方程为F[i, v] = max{F[i − 1, v ]}，对比于0-1背包问题，也就是不放第 i 件物品的情况，所以上述状态转移方程可以表示出每种物品取 0 件、取 1 件、取 2件……直至取 ⌊V /Ci⌋ 件等情况
3、简单优化
若两件物品 i、j 满足 Ci ≤ Cj 且 Wi ≥ Wj，则将可以将物品 j 直接去掉，不用考虑
4、把完全背包问题转化为 01 背包问题来解决
考虑到第 i 种物品最多选 ⌊V /Ci⌋ 件，于是可以把第 i 种物品转
化为 ⌊V /Ci⌋ 件费用及价值均不变的物品，然后求解这个 01 背包问题。这样的做法完全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为 01 背包问题的思路：将一种物品拆成多件只能选 0 件或 1 件的 0-1 背包中的物品

//二维数组完全背包问题
int CompletePack(vector<vector<int>>& dp, vector<int>& C, vector<int>& W, int& V)
{
    int num = C.size() - 1;
    for (int i = 1; i <= num; i++)
    {
        for (int v = 1; v <= C[i]; v++) {
            dp[i][v] = dp[i - 1][v];
        }
        for (int v = C[i]; v <= V; v++)
        {
        	int tmp = max(dp[i-1][v-C[i]] + W[i], dp[i][v-C[i]] + W[i]);
            dp[i][v] = max(dp[i-1][v], tmp);
            k++;
        }
    }
    return dp[num][V];
}

int main()
{
    vector<int> C = { 0,3,9,10 };
    vector<int> W = { 0,10,1,1 };
    int N = 3;
    int V = 8;
    vector< vector<int>> dp(N + 1, vector <int>(V + 1, 0));
    cout << "Maximum value is：" << CompletePack(dp, C, W, V) << endl;
    
    return 0;
}

//一维数组完全背包问题
int CompletePack(vector<int>& dp, vector<int>& C, vector<int>& W, int& V)
{
    int num = C.size() - 1;
    for (int i = 1; i <= num; i++)
    {
        for (int v = C[i]; v <= V; v++)//一维数组，但是递增顺序
        {
        	dp[v] = max(dp[v], dp[v - C[i]] + W[i]);
        }
    }
    return dp[V];
}

int main()
{
    vector<int> C = { 0,3,9,10 };
    vector<int> W = { 0,10,1,1 };
    int N = 3;
    int V = 8;
    vector<int> dp(V + 1, 0);
    cout << "Maximum value is：" << CompletePack(dp, C, W, V) << endl;
    
    return 0;
}

多维背包问题

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 Mi 件可用，每件耗费的空间是 Ci，价值是 Wi。
求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

多维背包问题的状态转移方程：
F[i，v] = max{F[i − 1, v − kCi] + kWi | 0 ≤ k ≤ Mi}

对比一下完全背包问题：
F[i, v] = max{F[i − 1, v − kCi] + kWi | 0 ≤ kCi ≤ v}
看起来非常相似，条件有所不同。

• 多维背包问题的条件是物品的件数是有限个，所以0 ≤ k ≤ Mi，k用来限制件数。
• 完全背包问题的条件是物品的件数是无限个，所以0 ≤ kCi ≤ v，k用来保证放入背包中物品的容量之和不会超过背包容量。
• 其余相同。

//二维数组多维背包问题
int MultiplePack(vector<vector<int>>& dp, vector<int>& C, vector<int>& W, vector<int>& K, int& V)
{
    int num = C.size() - 1;//物品数量
    for (int i = 1; i <= num; i++)//i初始值为1，为了对应第一个物品
    {
        for (int v = 1; v <= V; v++)//二维数组，此时循环选择递加操作；
        {
        	if(C[i] > v) {
				dp[i][v] = dp[i-1][v];
			} else {
	            int k = 0;
	            while (k <= K[i] && k * C[i] <= v)
	            {
	                dp[i][v] = max(dp[i][v], dp[i - 1][v - k * C[i]] + k * W[i]);
	                k++;
	            }
            }
        }
    }
    return dp[num][V];
}


int main()
{
    //数组C和W前面添加一个0，是为了方便“下标i 对应 第i个物品”
    //数组C和W存储了5个物品的数据
    vector<int> C = { 0,2,11,6,5,4 };//费用，即物品体积
    vector<int> W = { 0,6,3,5,4,6 };//价值
    vector<int> K = { 0,3,6,2,5,1 };//物品件数
    int N = 5;//物品数量
    int V = 10;//背包容量
    vector<vector<int>> dp(N + 1, vector<int>(V + 1, 0));//二维数组
    cout << "Maximum value is：" << MultiplePack(dp, C, W, K, V) << endl;

    return 0;
}