0-1背包问题（详细注释）

0-1背包问题是背包问题的基础，也是经典算法中动态规划与分支限界法的一个事例引入，了解0-1背包问题将有助于我们更进一步了解算法。

#include 
#include 
using namespace std;

struct Goods {
	int weight; // weight为商品对应质量
	int value; // value为商品对应价值
	Goods(int w = 0, int v = 0) {
		weight = w;
		value = v;
	}
};

void BasicalPacket() {
	cout << "Please input the number of goods: " << endl; 
	int numberGoods = 0;  cin >> numberGoods; // 输入商品的数量
	Goods* goods = new Goods[numberGoods];
	cout << "Please input the weight and value of each goods: " << endl;
	for (int i = 0; i < numberGoods; i++) 	cin >> goods[i].weight >> goods[i].value; // 输入商品的质量与价值
	
	// 0-1背包问题的一个重点是对dp的初始化 因为在状态转移方程中需要用到之前的数据
	cout << "Please input the capacity of packet: " << endl;
	int packet = 0; cin >> packet; // 输入背包的重量
	vector> dp(numberGoods, vector(packet + 1, 0)); // dp对应的是在遍历某物品(对应第一维数据） 背包质量(对应第二维数据)的情况下
																	 // 背包所对应的价值
																	 // 此时先将dp对应的全部元素初始化为0
	for (int i = 0; i < numberGoods; i++) dp[i][0] = 0; // 当背包质量为0的情况下 对应的背包价值应该全部都是0
	// 当背包质量大于第一件商品的质量时 所对应的背包价值应为第一件商品对应的价值
	for (int j = goods[0].weight; j <= packet; j++) dp[0][j] = goods[0].value;
	
	 
	for (int i = 1; i < numberGoods; i++) {
		for (int j = 1; j <= packet; j++) {
			if (j < goods[i].weight) dp[i][j] = dp[i - 1][j]; // 在背包质量小于该商品的情况下 该背包对应的价值是不加入该商品时的价值
			else {
				
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - goods[i].weight] + goods[i].value); 
			}
		}
	}
	cout << "0-1 Packet's maximum is : " << dp[numberGoods - 1][packet];
	
}

void main() {
	BasicalPacket();
	return;
}

注：非常感谢宝藏网站的启发 对小白学习基础知识极为友好！