CCF 202209-2 背包问题

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。

无限拿取的背包问题

for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
        {
			if(j>=t[i])
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);
			else
				dp[i][j]=dp[i-1][j];
        }

通常n个物品，空间为w背包问题中，我们创建大小为dp[n+1][w+1]的二维数组，并全部初始化为0，这样可以有效避免数组在边界时[i-1]的越界问题。
当j<t[i]时,包含物品i时空间为j的背包能储存的最大空间为dp[i-1][j]
当j>=t[i]时,包含物品i时空间为j的背包能储存的最大空间为max(dp[i-1][j],dp[i-1][j-t[i]]+v[i])

个数限制的背包问题

for(int i=1;i<=m;i++)
		for(int j=n;j>=t[i];j--)
			dp[j]=max(dp[j],dp[j-t[i]]+v[i]);

当每一个物品只有一个时，需要注意j 从大到小遍历，防止出现小物品重复拿的现象。