【CSP CCF记录】202209-2 何以包邮

题目

过程

0-1背包问题

有N件物品和一个容量是V的背包。每件物品有且只有一件。

第i件物品的体积是v[i]，价值是w[i]。

求解将哪些物品装入背包可使这些物品的总体积不超过背包容量，且总价值最大。

朴素0-1背包通解

状态定义：

本质上就是从i各物品中选择一定数量的物品在一定空间限制的前提下，求这些物品的最大总价值。我们可以定义一个二维数组dp[i][j]，这个数组的值就表示从前i件物品进行选择，在不超过容量j的前提下所满足最大的物品总价值。

确定初始状态：

当i=0时，表示只在前0件物品中做选择，也就是一件物品都不考虑，这种情况下不管背包容量为多少，能装的最大价值都是0；当j=0时，表示背包容量为0，这种情况下不管考虑前几件物品，都不能将其装入背包，即能装的最大价值也是0。

状态转移方程：

对于第i件物品，设它的所占容量为v[i]，价值为w[i]。

若当前背包的总空间j不能容纳第i件物品，就不能将第i件物品放入背包，此时背包内最大价值就应该等于前i-1件物品的总价值，即dp[i - 1][j]，那么就去前面查一下已经计算出的dp[i - 1][j]是多少，即dp[i][j] = dp[i - 1][j]。

若当前背包总空间j能容纳第i件物品，那就需要考虑一个问题：虽然当前背包能装下第i件物品，我一定要把它装进去吗？当然是不一定，如果这样考虑就变成了贪心算法（很容易理解）。因为第i件物品装进去虽然会增大背包的总价值，但同时也减少了背包的可用容量，可以这样理解：之前已经从前i-1件物品中选择了一部分放入了背包，如果此时放入第i件物品，就可能（并不是一定）需要从背包中已经放入的物品中再取出一部分，这样其实是增大背包总价值的同时也减少了总价值。所以需要先衡量第i件物品放进去和不放进去哪个总价值更大。分为以下两种情况考虑：

• 将其放入背包，此时背包内就已经用掉了w[i]的容量，且最少有v[i]的价值了，那么剩余j - w[i]的容量最多能装多少价值的物品呢？就需要去查查已经计算出的只考虑前i-1件物品时能装的最大价值dp[i - 1][j - w[i]]是多少，这样算完后总价值就表示为dp[i][j]= dp[i - 1][j-w[i]]+v[i]。
• 不将其放入背包，此时背包内总价值还是前i-1件物品的总价值，即dp[i][j] = dp[i - 1][j]。  

 取二者的最大值：dp[i][j] = max{dp[i - 1][j - w[i]] + v[i] , dp[i - 1][j]}

参考：http://t.csdnimg.cn/iP8bV

本题思路

参考：http://t.csdnimg.cn/ZFT60

http://t.csdnimg.cn/f024o

联想到动态规划0-1背包问题。

用所有书的价格减去最低包邮价格就是背包的大小temp，换句话说就是让删除的书的价格总和尽可能大。

两层循环，第一层循环为每本书（物品）（i=1,2,...n），第二层循环当前删除书本价格（背包容积）（j=1,2,...temp）。

三种情况

j<a[i]，若背包不能容纳第i件物品，dp[i][j]=dp[i-1][j]

j>=a[i]，若背包能容纳第i件物品，以下两种情况取较大值。

• 如果不放该物品，则dp[i][j]=dp[i-1][j]；
• 如果放该物品，则dp[i][j]=dp[i-1][j-a[i]]+a[i]；

代码

#include<bits/stdc++.h>
using namespace std;
int n,x;
int main()
{
	cin>>n>>x;
	vector<int>a(31);//每本书的价格
	int sum=0; 
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	int temp;
	temp=sum-x;
	int dp[31][100001];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=temp;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=a[i])
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j-a[i]]+a[i]);
			}
		}
	}
	int result=0;
	result=sum-dp[n][temp];
	cout<<result<<endl;
	return 0;
}

结果