背包

背包问题

1. n个物体，体积Ci，价值Wi，有一个容量为V的包，求价值最大。

• 前i个物体放入容量为v的背包可以获得的最大值

  • F[i,v]=max{F[i-1,v],F[i-1,v-Ci]+Wi}
  • 第i个要么不放，要么放
  • O(Vn)

• 因为只跟前一个状态i-1有关，空间可以优化.

  • F[v]跟F[v-Ci]有关，也就是数组后面的跟前面的有关，如果顺序计算，那么前面是更新后的，在计算后面的就不是前一次的状态的了，所以要递减来计算。

  • for(int i=0;i<n;i++){
    	for(int j=V;j>=Ci;j--){
    		……	
    	}
    }

• 初始化：

  • F[0]=0，其余MIN,
  • 如果不要求签好装满背包，均为0

  ---

  每个物品无限次使用

  • F[i,v]表示前i个物体恰好放入一个容量为v的背包。
  • F[i,v]=max{F[i-1,V-kCi]+kWi}|1<=kCi<=V}

• 跟上面的区别主要在于，这里的取或者不取变成了，要取多少个，0个就是不取，直到V/Ci。

• O(nVsum(V/Ci))

• 优化：

  for(int i=0;i<n;i++){
  	for(int v=Ci;v<V;v++){
  		F[v]=max(F[v],F[v-Ci]+Wi)
  	}
  }

  这里和01背包只是内循环的次序不同。

  F[i,v-Ci]+Wi，表示的是在原来（不管第i件物品已经选了多少个了，只要不超过总容量V）的基础上，在添加一件，

多重背包

第i个物品的数量是Mi。其余一样。

Mi可以拆分为1,2, 2^2,*** 2^k, Mi-2^k+1;这一点可以记住，0- 2 ^ k-1 可以组成 2^ k - 1的所有数字。