背包问题

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution_back
{
	//vector<int> vs{ 0,2,4,3,7 };
	//vector<int> ws{ 0,2,3,5,5 };
	vector<int> vs{-1,-1,1,6};
	vector<int> ws{-1,1,-1,6};
	int P[4]{0,2,3,4}; 
	int V[4]{0,3,4,5};
	int M[4]{0,4,3,2};

public:
	void test_ks()
	{
		//01背包测试
		//cout << ks1(4,10) << endl;
		//cout << ks2(4, 10) << endl;
		//cout << ks3(4, 10) << endl;
		//cout << ks4(4, 10) << endl;
		////完全背包测试
		//cout << ks5(4, 10) << endl;
		////多重背包测试
		//cout << ks6(3, 15) << endl;
		//cout << ks7(3, 15) << endl;
		cout << ks8(4, 4) << endl;
	}

	//01背包 --- 递归解法
	int ks1(int n, int m)
	{
		int result = 0;
		// 递归结束条件
		if (n == 0 || m == 0) return result;
		else if (m < ws[n]) //如果装不下
			result = ks1(n - 1 ,m);
		else
			result = max(ks1(n - 1, m), ks1(n - 1, m - ws[n]) + vs[n]);
		return result;
	}

	//01背包 --- 动态规划：自上而下填表法
	int ks2(int n, int m)
	{
		//初始化操作
		vector<vector<int>> dp(n + 1,vector<int>(m + 1 , 0));
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= m; ++j)
			{
				if (j < ws[i]) dp[i][j] = dp[i - 1][j];
				else
					dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - ws[i]] + vs[i]);
			}
		}

		return dp[n][m];
	}

	//01背包 --- 动态规划：自底向上的填表方式
	// 滚动数组 --- 将二维压缩到一维
	//形式1
	int ks3(int n, int m)
	{
		//初始化操作
		vector<int> dp(m + 1 , 0);
		for (int i = 1; i <= n; ++i)
		{
			for (int j = m; j >= ws[i]; --j)//这里逆序遍历j，以到达更优就覆盖的过程，循环结束条件是当放不进去的时候就结束内层循环
				dp[j] = max(dp[j] , dp[j - ws[i]] + vs[i]);
		}

		return dp[m];
	}

	//滚动数组 --- 形式2
	int ks4(int n, int m)
	{
		//声明一个dp[2][m + 1]的只有两行的二维数组
		vector<vector<int>> dp(2, vector<int>(m + 1, 0));
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				if (j < ws[i])
					dp[i % 2][j] = dp[(i - 1) % 2][j];
				else
					dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - ws[i]] + vs[i]);

		return max(dp[0][m],dp[1][m]);
	}

	//完全背包问题
	//物品的数量是无限次可以拿取的，我们在01背包的基础进行修改。正好利用01背包的空间优化算法，这时候
	//我们不逆序执行状态转移方程，而是正序执行，正好可以实现每种武平的重复利用，即相当于每种物品有无限个

	int ks5(int n, int m)
	{
		vector<int> dp(m + 1, 0);
		for (int i = 1; i <= n; ++i)
			for (int j = ws[i]; j <= m; ++j)
				dp[j] = max(dp[j] , dp[j - ws[i]] + vs[i]);
		return dp[m];
	}

	int ks51(int n, int m)
	{
		vector<int> dp(m + 1, 0);
		for (int i = 1; i <= n; ++i)
			for (int j = ws[i]; j <= m; ++j)
				dp[j] = max(dp[j], dp[j - ws[i]] + vs[i]);
		return dp[m];
	}

	//多重背包问题
	//介于01背包和完全背包之间的算法问题，物品的数量有限次，增加一个物品数量数组M，物品价值数组P,物品重量数组V
	//递推式： dp[i][j] = max{dp[i - 1][j - V[i]*k] + P[i]*k}; (0 <= k  <= M[i]  && 0 <= k * V[i] <= j);
	//这个递推式相对于完全背包而言，就是多了一个限制条件：0 <= k  <= M[i] ；其他都是一样的；

	// 多重背包问题 --- 简单递归
	int ks6(int n, int m)
	{
		int result = 0;
		if (n == 0 || m == 0) return result;
		else if (m < V[n]) result = ks6(n - 1, m);
		else
		{
			for (int k = 0; k <= M[n] && k * V[n] <= m; ++k)
			{
				int temp = ks6(n - 1, m - V[n] * k) + P[n] * k;
				if (result < temp)
					result = temp;
			}
		}

		return result;
	}

	//多重背包问题 --- 动态规划空间优化算法
	//note：这里要将补的0删除掉
	int ks7(int i , int t)
	{
		vector<int> newResults(t + 1);
		// 开始填表
		for (int m = 0; m <= i; m++) 
		{
			// 考虑第m个物品
			// 分两种情况
			// 1： M[m] * V[m] > T 则可以当做完全背包问题来处理
			if (M[m] * V[m] >= t) {
				for (int n = V[m]; n <= t; n++) {
					newResults[n] = max(newResults[n], newResults[n - V[m]] + P[m]);
				}
			}
			else {
				// 2： M[m] * V[m] < T 则需要在 newResults[n-V[m]*k] + P[m] * k 中找到最大值，0 <= k <= M[m]
				for (int n = V[m]; n <= t; n++) {
					int k = 1;
					while (k < M[m] && n > V[m] * k) {
						newResults[n] = max(newResults[n], newResults[n - V[m] * k] + P[m] * k);
						k++;
					}
				}
			}
		}

		return newResults[t];
	}



	//滚动数组 --- 形式2
	int ks8(int n, int m)
	{
		//声明一个dp[2][m + 1]的只有两行的二维数组
		vector<vector<int>> dp(2, vector<int>(5101, 0));
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j <= m; ++j)
			{
				if (ws[i] < 0)
				{
					dp[i % 2][j - ws[i]] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - ws[i]] + vs[i]);
					m -= ws[i];
				}
				if (j < ws[i])
					dp[i % 2][j] = dp[(i - 1) % 2][j];
				else
					dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - ws[i]] + vs[i]);
			}
		}

				

		return max(dp[0][m], dp[1][m]);
	}

};