[背包] 背包有关于 恰好,不超过,至多问题的总结

前言

会考虑如何证明

1. 不超过 1.1 方案数

对于方案数，我们需要先初始化 f ( 0 ) [ i ] = 1 f(0)[i] = 1 f(0)[i]=1 然后从 v v v到 m m m的倒序转移即可

for(int i=0;i0 要么就是从0->m
 
3.1 方案数 
除了 
     
      
       
       
         f 
        
       
         [ 
        
       
         0 
        
       
         ] 
        
       
         [ 
        
       
         0 
        
       
         ] 
        
       
         = 
        
       
         1 
        
       
      
        f[0][0] = 1 
       
      
    f[0][0]=1之外其他全部为 
     
      
       
       
         0 
        
       
      
        0 
       
      
    0
 
然后我们倒序状态转移
 
	f[0] = 1;
	for(int i=1;i=0;j -- )
			f[j]+=f[j-v ?  0];
 
3.2 最值问题 
除了 
     
      
       
       
         f 
        
       
         [ 
        
       
         0 
        
       
         ] 
        
       
         = 
        
       
         0 
        
       
      
        f[0]=0 
       
      
    f[0]=0外,其他全部是 -INF 只会求最小值
 
然后我们倒序状态转移
 
	memset(f,-0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i=0;j -- )
			f[j] = min(f[j],f[j-v ? 0 ]+w);