第十三周小结

  这周主要看了背包问题的博客。背包问题有多种类型：01背包，完全背包，多重背包，分组背包等。这类问题着重于对题目的分析，找到其对应的背包类型。下面总结一下这周看过的题中体会较深的题目。

1.P1049 [NOIP2001 普及组] 装箱问题

题意：有一个箱子容量为V，同时有n个物品，每个物品有一个体积。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

题解：
  其实第一次看这道题时想到的是搜索，但后来仔细想了想，背包也能做，而且做起来比搜索简单，只是理解要转换一下。
  题目求出最小的剩余空间，也就是要求出最大的可装重量。如果把一个物体的重量当作它的价值，那么题目就可以转变为一个基本的01背包问题。一个箱子有两种状态：装与不装。记第i个箱子重量为w[i]，对于任意重量m的最大价值记为 f (m) ，于是可得状态转移方程 f（m）= max ( f ( m - w[i] ) + w[i], f (m) )。简单的01背包问题，难度不大。

2. P1455 搭配购买

题意：一种搭配即为一个集合，求不超过给定价值集合的价值最大值。

题解：
  这道题在做并查集练习时做过，当时做的的时候还没有01背包的概念，写的代码比较繁琐，现在看来用01背包做更加简单，于是在此整理一下。
  这是一道并查集+01背包题，01背包的限制条件为买A必须买B，故可以用并查集将几个物品合成一个大物品，然后再用01背包做即可。

for(int i=1; i<=tot; i++)
		for(int j=w; j>=newp[i]; j--) //滚动数组
			f[j]=max(f[j],f[j-newp[i]]+newv[i]);

3. The Values You Can Make

题意：有n个硬币，硬币有对应的价值，现在要挑出一些硬币组成k元，输出挑出的硬币可以组成钱的不同价值。

题解：
该题和背包比较相似，不过又加了个状态，就是是否可以组成s，那么状态dp[i][j][p]为考虑到第i个数，当前所有数的和为j，组成和为p的子集是否可能。
于是可以得到状态转移关系：
如果不使用第i个数，dp[i][j][p]=dp[i-1][j][p]
如果使用第i个数但子集不取他，dp[i][j][p]=dp[i-1][j-ci][p]
如果使用第i个数且子集取他，dp[i][j][p]=dp[i-1][j-ci][p-ci]。

代码：

#include<bits/stdC++.h>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
const int INF_INT  = 0x3f3f3f3f;
const ll INF_LL  = 1e18;
const int MAXN =1e5+5;
const int MAXM = 1015;
int n,k;
int c[505];
bool dp[505][505][505];
vector<int> ans;
int main()
{
      while(cin>>n>>k)
    {
    
        dp[0][0][0]=1;
        for(int i=1;i<=n;i++)
        {
      cin >> c[i]; }

        for(int z=1;z<=n;z++)
        {
      for(int i=0;i<=k;i++)
            {
    
                for(int j=0;j<=i&&j<=k;j++)
                {
     if(dp[z-1][i][j] ||(i>=c[z]&&dp[z-1][i-c[z]][j]) || (j>=c[z]&&dp[z-1][i-c[z]][j-z[c]]))
        dp[z][i][j] = 1;
                }
            }
        }
        for(int i=0;i<=k;i++)
        {
     if(dp[n][k][i])
            {
     ans.push_back(i); }
        }
        cout<<ans.size()<<endl;
        for(int i=0;i<ans.size();i++)
        {
    cout<<ans[i]<<" ";}
        cout<<endl;
    }
}

4. P1284 三角形牧场

题意：有 n 块木板，每块的长度 l[i]都是整数，求用所有的木板围成一个三角形使得牧场面积最大。

题解：
我们可以用f[k][i][j]表示用前k个木板能否围成两边长为i,j的三角形。

开始我想用f[a][b][c表示三边长为a,b,c的三角形。但是一直报错。后来看了题解，原来三角形的边长的最大值=4040/2=800，800800*800显然太大，所以不可行。

把第k个木板放在i这条边中：
用前k-1个木板围成i-a[k]和j的三角形，即f[k-1][i-a[k]][j]。
把第k个木板放在j这条边中：f[k-1][i][j-a[k]]。
把第k个木板放在第三条边中：f[k-1][i][j]。

于是得到状态转移方程：
f[k][i][j]=f[k-1][i-a[k]][j] || f[k-1][i][j-a[k]] || f[k-1][i][j];

最后，枚举i和j，判断能否构成三角形。

代码：

#include<bits/stdc++.h>
const int N=50;
const int L=800+10;
using namespace std;
int n,a[N],sum;
double ans;
bool f[L][L];
bool check(int x,int y,int z) 
{
      if(x+y>z&&x+z>y&&y+z>x) return 1;
	return 0;
}
double work(double x,double y,double z)
{
      double p=(x+y+z)/2;
	return sqrt(p*(p-x)*(p-y)*(p-z));
}
int main()
{
      int i,j,k;
	cin>>n;
	for(i=1;i<=n;i++){
    cin>>a[i]; sum+=a[i];}
	f[0][0]=1;
	for(k=1;k<=n;k++)
	  for(i=sum/2;i>=0;i--)
	    for(j=sum/2;j>=0;j--)
	    {
     if(i-a[k]>=0&&f[i-a[k]][j]) f[i][j]=1;
	      if(j-a[k]>=0&&f[i][j-a[k]]) f[i][j]=1; 
		}
	ans=-1;
	for(i=sum/2;i>0;i--)
	  for(j=sum/2;j>0;j--)
	  {
     if(!f[i][j]) continue;
	  	if(!check(i,j,sum-i-j)) continue;
	  	ans=max(ans,work(i,j,sum-i-j));
	  }
	if(ans!=-1) cout<<(long long)(ans*100)<<endl;
	else cout<<ans<<endl;
	return 0;
}

5. POJ 1384(完全背包变形)

题意：
给出小猪存钱罐的最初重量和装满重量，再给出一些金币，金币有价值与重量，求小猪装满的情况下价值最小是多少。

题解：
这道题是多重背包思想转换成01背包。
在01背包中，考虑容纳 i 个物体的时候，有选择和不选择两种可能。
但是在多重背包问题中，我们可以选择多次。

所以可以得到转移方程：
dp[i][j] = max( dp[i-1][j], dp[i][j-weight[i] ] + value[i] )

代码：

for( int i = 0; i < nObject; i++)
{
    
        for( int j = weight[i]; j <= sumweight; j++)
        {
    
               dp[j] = max[dp[j], dp[j-weights[i]] + value[i];
        }
}

总结：
  这两周因为有各种考试，在背包问题上花的时间较少，感觉还需要加强练习，虽然结课了，但我的ACM学习才刚刚开始，我还需要再接再厉，暑假继续加油！