|
|
沙发
楼主 |
发表于 2015-11-5 15:12:27
|
只看该作者
[ 本帖最后由 diggersun 于 2015-11-5 15:16 编辑 ]\n\ndp之01背包
01背包，做为背包中最基础的一类背包，必须要掌握好，当然我这里说的掌握好，并不是说，你横扫hdu或者poj等oj上01背包模板题就可以的，记得很久以前，刚开始做背包问题，一天在hdu水了七八道，就自以为背包就是个模板，唉，真心不知道当时的自己是有多肤浅..........
01背包的动态转移方程，背包九讲上有详细的讲解，这里不再复述，就想说下，一维的和二维的转移方程都需要深刻理解，不要觉得任何时候01背包都可以转化为1维的数组
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+val);
dp[j]=max(dp[j],dp[j-v]+val);
此外，还想说下，01背包为什么体积要从v---0？这个问题，背包九讲上是说可以每件物品只拿一次，恩，我觉得可以自己推推，这样理解会更加深刻.......
1、UVA624（记录路径问题）
总得来说，不管是01背包还是完全背包，其动态转移每次只有两种状态在转移，就说这道题目，
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+val[i]) 对于dp[j]来说，它只能使由两个状态中的一个转移过来的，要么取一件，要么不取，那么我们再开一个二维数组s[j]，0表示不取，1表示取，那么不取是dp[i-1][j]，取是dp[i-1][j-v]+val[i]；这样，数组s[j]就记录下了每次动态转移的方向，在递归调用，打印路径，结果就出来了，具体可以看[url]http://www.cnblogs.com/ziyi--cao[/url] ... /04/10/3012578.html
2、UVA562（平分钱币问题）
题目大意：给定n个硬币，要求将这些硬币平分以使两个人获得的钱尽量多，求两个人分到的钱最小差值。
这类问题的关键就在平衡，而就这到题目而言，01背包本身求的就是在体积小于等于sum的情况下的最大值，那么这些硬币本身既当体积又当价值，把总价值求出来/2，再套用模板......可以说比较水的平衡问题，具体看：[url]http://www.cnblogs.com/ziyi--cao[/url] ... /04/10/3012755.html
3、组成n块钱，有多少种的问题
这类题目，一般是这样描述的：给你n块钱，有m种钱币，每种钱币只能用一次，问组成n块钱有多少种方法........
对于这类题目，我更多的感受是觉得是到递推题，其实，有好多的dp都是一个递推，然后记录更新状态的过程，要组成dp[j],那么假设有一个5快的钱币，那么首先要判断dp[j-5]有没有组成，这里我比较喜欢用0表示没有这个状态，>0表示这个状态存在，那么在初始化dp数组的时候，dp[0]=1；然后套用背包模板，其动态转移方程（倒不如说递推式）为dp[j]+=dp[j-5]；
上面是常规题目，下面为01背包的变种题：
4、poj2184（两个属性最大和，平移问题）
题意：给定两个属性,求这两个属性的和的最大值.........
思路：对于这种题目，我们可以尝试将一个属性当作容量，另一个属性当作价值，然后考虑dp.......这个题目属性还可以是负数，那么可以采取平移1000个单位，使其不存在负数问题。将第一个属性往后平移1000个单位，然后推导其动态转移方程，若是dp，代表当加入第一个属性加到i时，符合题意的第二个属性的最大值......题意是两个属性的和的最大值，那么动态转移方程必然不是dp[j]=max(dp[j],dp[j-s[0]]+s[1]），因为这个动态转移方程固然可以求出第二个属性的最大值，但别忘了题意要求第一个属性与第二个属性的和的最大值，那么，第一个属性平移了1000个单位，在考虑动态转移时，是必须要将这个考虑进去的。可以开一个a数组记录路径，然后根据题意，
动态转移方程应该为dp[j]=max(dp[j]-a[j]*1000,dp[j-s[0]]+s[1]-(a[j-s[0]]+1)*1000),一开始a数组全部赋值为0，所以需要a[j-s[0]]+1.....因为它新加入了一个值。考虑这个方程，dp数组的初始全部赋值为负无穷大，dp[0]=0。
注意一点，在历遍查找最大值的时候，dp>0,i-a*1000>0
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define maxx 1000005
int s[maxx][2],dp[maxx],a[maxx];
int main()
{
int n;
while(scanf("%d",&n)>0)
{
int sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d %d",&s[0],&s[1]);
if(s[0]<0&&s[1]<0)
{
i--;
n--;
continue;
}
s[0]+=1000;
sum+=s[0];
}
memset(a,0,sizeof(a));
for(int i=0;i<=sum;i++)
dp=-maxx;
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=s[0];j--)
if(dp[j]-a[j]*1000<dp[j-s[0]]+s[1]-(a[j-s[0]]+1)*1000)
{
dp[j]=dp[j-s[0]]+s[1];
a[j]=a[j-s[0]]+1;
}
}
int maxn=0;
for(int i=1;i<=sum;i++)
if(maxn<dp-a*1000+i&&dp>=0&&i-a*1000>=0)
maxn=dp-a*1000+i;
printf("%d\n",maxn);
}
return 0;
}
5、hdu2639（第k优解问题）
题意：给出一行价值，一行体积，让你在v体积的范围内找出第k大的值.......（注意，不要 和它的第一题混起来，它第一行是价值，再是体积）
思路：首先dp[j]代表的是在体积为i的时候第j优解为dp[j]......那么，我们就可以这样思考，i对应体积，那么如果只是一维的dp，代表的应该是体积为i时的最大值，那么同理，dp[1]代表的是体积为i时的最大值，那么我们就可以退出两种动态，dp[m],dp[i-s[0]][m]+s[1].....然后把这两种状态开个两个数组分别保存起来，再合并出体积为i时的前k优解......依次后推，直到dp[v][k].......
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define max(x,y) x>y? x:y
typedef int ss;
ss dp[1005][100],s[1005][2];
ss a[50],b[50];
int main()
{
int text;
scanf("%d",&text);
while(text--)
{
ss n,v,k;
scanf("%d%d%d",&n,&v,&k);
for(ss i=1;i<=n;i++)
scanf("%d",&s[1]);
for(ss i=1;i<=n;i++)
scanf("%d",&s[0]);
memset(dp,0,sizeof(dp));
if(k==0)
{
printf("0\n");
continue;
}
for(int i=1;i<=n;i++)
{
for(int j=v;j>=s[0];j--)
{
for(int m=1;m<=k;m++)
{
a[m]=dp[j][m];
b[m]=dp[j-s[0]][m]+s[1];
}
int x=1,y=1,w=1;
a[k+1]=b[k+1]=-1; //这个地方要注意，因为有可能a或者b数组先比较完
while(w<=k&&(x<=k||y<=k))
{
if(a[x]>b[y])
{
dp[j][w]=a[x++];
}
else
{
dp[j][w]=b[y++];
}
if(w==1||dp[j][w]!=dp[j][w-1]) //这是去重.....
w++;
//printf("111\n");
}
}
}
//for(int i=1;i<=k;i++)
printf("%d\n",dp[v][k]);
}
return 0;
}
6、hdu3644（带限制的01背包）
题意：买东西，每个东西有三个特征值，p代表价格，q代表你手中钱必须不低于q才能买这个物品，v代表得到的价值。
mark：又是变种01背包，每做一个变种的，就是一种提高。。
按照q - p以由大到小的顺序排序，然后进行01背包的DP即可。
|
|
发表于 2015-11-5 15:08:43
收藏
发表于 2015-11-6 13:56:02
