Bone Collector-0-1背包

update@2011-08-05

memset(dp[0],0,sizeof(int)*(v+1));//不放任何物体不管背包容量多少 价值都是0
for(i = 1;i <= n;i++){
    //处理第i 个物体，在当前背包容量为j的时候选还是不选这个物体
    for(j = 0;j <= v;j++){//枚举每个容量
        if(bone_volume[i] > j){//这个物体肯定是不能放在容量为j的背包里的
            //不知道为什么有些解题报告没有这个判断（大部分是有的）
            //如果j < bone_volume[i]，相减之后就小于0了
            dp[i][j] = dp[i-1][j];
        }
        else{//如果体积刚好等于剩余的容量也不一定会被放进去
             //因为可能有其它几个物体组合之后的价值比这个单个物体的高
            dp[i][j] = mymax(dp[i-1][j],dp[i-1][j-bone_volume[i]]+bone_weight[i]);
        }
    }
}//结果保存在 dp[n][v]中，即对前n个物体做出取舍后的最优解



HDU -Bone Collector
都说它很水，我却搞了半天 = =.不是状态方程什么的，说到底是没明白dp的思想
01背包是背包中最基础的。之前一直不能理解的是 i=1的时候怎么做取舍，选第一个还是不选第一个？