寒假的第一次训练的第三题。

一开始确实就是没什么思路，然后听说是01背包，就以为是讨论一个骨头在或者不在这个背包里，然后复杂度就是O(2^n),这肯定不对啊，数据规模1000呢。

然后就去看学长发的背包九讲，知道了是动态规划。然后仔细读了两遍这个核心代码和基本思想。意思大概就是说，放第i个的时候，把“把前i-1个放到背包里”这件事进行封装。也就是用f（i，j）表示把第i个（注意是第i个！）骨头放到体积余剩为j的背包里面，然后这个背包最多的总价值可以是多少。

F[0,0..V ] = 0

for i = 1 to N

for v = Ci to V

F[i,v] = max{F[i−1,v],F[i−1,v−Ci] + Wi}

给的核心代码是这一段，但是这个代码其实是默认的每个物体的体积vi都是小于背包总体积V的。然后就是从放一个开始，一层一层得记录。问题就是，按照这个代码，如果第i个物体的体积是大于总体积的，内层循环将不会进行。然后二维数组下一层进行时，用到的上一层的数据将都是初始化的时候的0,（即数据传到这一层就中断了，也就从新开始计数）。

所以改了一下这一段：

for(int i=1;i<=n;i++)//一共有n个骨头

{

for(int j=0;j<=s;j++)

{

if(j>=v[i])f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+moy[i]);

else f[i][j]=f[i-1][j];

}

}

相对于上一个，这一段虽然内层循环变长了，但是可以防止出现物体体积大于背包体积时出现的错误。

那段伪代码的意思应该是：

放第i块的时候，余剩的体积如果大于等于Vi（也就是这一块放得开），那就分别考虑这一块放和不放的情况。如果余生的体积小于Vi（也就是这一块骨头放不开了）那它的值就应该是不放这块的值，也就是f（i-1，j）。但是由于初始化的时候都是0，所以需要另外的判断语句。

另外这是从正常的往里面放的情况（递推）。还可以是我想知道f（n，v），我就要找max（f（n-1，v），f（n-1，v-vi）+wi）;然后再继续找下面，也就是递归函数的方法。

相比之下呢，递归是需要什么就去找什么，而递推这种方法就一定要找到正方向（我也不知道怎么形容这个词，就是这么个意思吧，这一段话我说的应该都不太清楚），像这道题放的第几个就是正方向，一个一个变多，一层一层接近最终解。

注：此题背包容量和骨头体积可能为0。

 

/* Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave … The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ? */ /* 1000 5 10 1 2 3 4 5 5 4 3 2 1 5 0 2 4 1 5 1 0 1 1 0 0 */ /* 第二行是这块骨头值多少钱，第三行是这块骨头占多大体积 */ //01背包问题 //背包容量可以为0，骨头所占空间也可以为0 #include #include #include #define N 1010 using namespace std; int moy[N]={0}; int v[N]={0}; int f[N][N]={0};//f[i][j]表示要放第i块骨头，余剩空间为j的时候，最优放法能获得的价值 void shuru(int n)//输入 { for(int i=1;i<=n;i++) { cin>>moy[i]; } for(int i=1;i<=n;i++) { cin>>v[i]; } } int main() { int T; cin>>T; while(T--) { int n,s; cin>>n>>s; shuru(n); for(int i=1;i<=n;i++)//一共有n个骨头 { /*if(v[i]>s) { for(int j=0;j<=s;j++) { f[i][j]=f[i-1][j]; } }*/ for(int j=0;j<=s;j++) { if(j>=v[i])f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+moy[i]); else f[i][j]=f[i-1][j]; } } cout<