SGU 104 Little shop of flowers

题意

插花,给你若干花瓶和若干把花,花瓶个数大于等于花的把数,每把花都不一样,要求你让每把花都插进花瓶里面,花瓶不一定每个都要用,但是你必须保证插完之后花的排列顺序和原来给出的一样。然后给了你一个花插进花瓶之后产生的美学价值对照表,要你设计一种方案使得这样插花所达到的美学价值最大。

思路

典型的背包问题,我们设计一个二维dp数组dp[i][j],令i表示当前已经考虑到第几把花,令j表示对于当前这把花我们插入到前j个花瓶,那么我们一把一把花处理,对于每把花枚举其插入每个花瓶的结果,同时要继承上一把花插入到这个花瓶之前的全部状态中最优的那个(因为要保证有序)。最后枚举dp[n][j]的j,找到最佳状态就好了。
接下来要考虑怎么输出最优方案,其实不难想,我们可以给dp数组加上一维或者单开一个pre[i][j]数组,与dp数组平行工作,保存当前状态的前置状态,最后顺着最佳状态不断回溯输出就搞定了。

代码

 

HDU 3466 Proud Merchants

这是个需要排序预处理的01背包问题(够sxbk),排序的基准是q-p小的在前。

至于为啥。。。我是可耻的翻了题解才知道怎么做的,这位讲的清楚明白:

http://blog.csdn.net/oceanlight/article/details/7866759

HDU 1028 Ignatius and the Princess III 拆分数问题(顺序无关型)

又是一个特定问题了,这个叫拆分数问题(不考虑顺序型)。解法如下(其实是扒来的):

¤动态规划解题思路:

¤定义状态:dp[x][n]表示只用整数 1~ x 表示出n有多少种方法。

¤状态转移方程:

¤dp[i][n]=dp[i-1][n]+dp[i][n-i]

¤边界条件:

dp[1][k]=1 (0<=k<=n)

因为对于0~n,只用1去表示的只有一种方法。

其(ren)实(hua)是这样,假如说我们像拆分7,那么我们就是用1~7的数来加合成7了,用1~7表示7可以分开两种看:用1~6表示7,和用1~7表示0,这两种情况,后面那个看起来很sxbk,其实就是7+0啦。然后1~6表示7我们还是不会算,这个又可以分解了,那就是用1~5表示7,和1+6(用1~6表示1),接下来再把1~5表示7拆分为1~4表示7和5+2(用1~5表示2,这会你应该看出来了,5+2中,5不能动只是肯定的,但是2已经不止一种表示方法了),接下来再拆1~4表示7为1~3表示和4+3,然后拆拆拆到1表示7,显然只有一种方法1111111,这样就到达了递推的终点,逐层返回就搞定了。

HDU 1114 Piggy-Bank

这个基本上还是01背包嘛,但是这回我把状态的判定条件设置为在一定重量的情况下,尽量让硬币的总价值更少。

HDU 2191 悼念512汶川大地震遇难同胞――珍惜现在,感恩生活

这个是一个多重背包问题,其实多重背包就是01背包,举个例子(其实是扒的):

¤像如果某件物品的重量为1,价值为2,数量为1000

¤我们就可以拆分成:

¤重量为1,价值为2的物品 重量为2,价值为4的物品

¤重量为4,价值为8的物品 …

¤重量为256,价值为512的物品

¤重量为489,价值为489*2的物品

简要地说,就是先拿二进制拆,拆出来1,2,4,8,16,32。。。这样的,等到拆不动了(剩下的不够下一个2进制整幂了),就把剩下的单独拿出来当成一个新物品,这样就不会丢解了。拆分完之后不就变成01背包了嘛。

HDU 2546 饭卡

这道题给我玩惨了,原因就是“hehe”那里没有加,后果是啥大家都知道。。。

其实是一个包装过了的01背包问题,既然>=5块时都能随便花,那么我就把最贵的那个留下,然后尽量把饭卡刷到还剩5块钱的程度(不一定是五块,但尽量靠近五块),然后再去买那个最贵的,一次性刷爆。(虽然还是有可能刷不爆的,但余额尽量小是真的),“尽量把饭卡刷到还剩5块钱的程度”,这个就可以转化为重量限定m-5,每个物品重量与价值相等情况下的01背包问题。

就这样。

POJ 3624 Charm Bracelet 顺便讲一下01背包

裸的01背包问题,是DP的基础题型了,没有太多好说的。

简要说一下01背包问题的状态转移特点:按两个基准纪录数据,第一个基准是我们从0~a号物品中选,第二个基准是选择的物品已经有了多少重量b,这样组成了dp数组dp[a][b],这个数组存储的是当前状态的价值是多少。接下来我们开始dp,对于每一个当前状态(最多选择到第n个物品,已经占用了w重量),我们是从两种先前状态中导出的:1.最多选择到n-1个物品(就是当前物品还没有考虑呢),占用重量w-x(x是第n个物品重量),在这个状态上,我们添加上第n个物品。2.最多选择到n-1个物品,占用重量w,在这个状态上,我们什么也不做,直接把他当成当前状态。

在这两种先前状态中选择最好的那个(有时候因为某些原因,只能选择一个,那就选唯一的那个就好),保存下来决定为当前状态,再供以后使用。

这样我们只要读取dp[i][j]的值,就是“选择1~i中的物品,重量限定为j,最高价值是?”这个问题的答案。(没有用滚动数组的话)

Scroll to top