分析：
（好题）背包，二进制的另一种应用（话说LZ貌似初中的时候也想
过这种组合方式额，不过n年后的现在早忘了�~），既：
1、2、4可以组合出所有小于8的数；
1、2、4、8可以组合出所有小于16的数；
1、2、4、8、16可以组合出所有小于32的数；
……
PS一个：
另外，看网上的代码，几乎都是用dp[i]来表示容量为i这个包包
可以装多少价值，递推公式为dp[j]=MAX(dp[j],dp[j-val[i]]+val[i])，
然后判断dp[i]是否==i，等于了，那么ans++；
对于这方法，菜鸟卖个萌�嗦点儿话�~：
1、用flag[i]标记i状态是否可达就行了，没必要求容量为i的包包
最大可以装多少val；（所以我的代码里面用的就是(状态now)=(状态now)
||(状态pre)）
2、对于这个方法呀，如果没有理解透的话，是容易粗事儿的�~~~，
也就有了：
"为什么我在进行判断的时候，用dp[i]>=i这个式子，
既if(dp[i]>=i) ans++，
这种方法写出来的代码也能ac呢？"
这种问题的出现(在一些blog里面看到的)。
对于这个，只能说这个题是个特例，是不管对于n种物体的哪种物体，
容量和val的比例总是恒定的，而且还是1:1的关系（注意这儿是1:1，而
不是1:2、1:3或者2:3之类的），既dp[j-a]+b中，a=b=val[i]，a:b==1:1，
所以才保证了，《如果容量为i的状态可达，那么最后dp[i]必定==i》
（因为a==b么）；
所以么必要用这个状态转移方程了，赶脚砍魔兽的刀用猪身上了�~~
Read full article from hdu2844 - Ice_Crazy的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment