【日常学习】【背包DP】codevs1014 装箱问题题解

以你之姓@ 2022-08-03 13:41 167阅读 0赞

转载请注明出处 来自CSDN用户ametake   
题目来自NOIP2011PJ4  
上题目

题目描述 Description

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述 Input Description

一个整数v，表示箱子容量

一个整数n，表示有n个物品

接下来n个整数，分别表示这n 个物品的各自体积

输出描述 Output Description

一个整数，表示箱子剩余空间。

样例输入 Sample Input

样例输出 Sample Output

这道题我们可以用最朴素的二重循环背包完成，但在这里学习到的是空间复杂度O(N)的一维背包DP  
  
简明解释：我们省略f\[i\]\[v\]，用f\[v\]表示第i次循环时容量为v时最大价值，即表示f\[i\]\[v\]。由于f\[i\]\[v\]要由f\[i-1\]\[v-ci\]推过来，因此必须采用倒着推，才能保证在我们求f\[v\]时，f\[v-ci\]中存储的是f\[i-1\]\[v-ci\]而非f\[i\]\[v-ci\]。  
对于这道题，我们只需要把体积同时当做体积和价值即可。  
那么代码君

//codevs1014 装箱问题 背包DP（一维）
    //copyright by ametake
    #include
      
       
    #include
       
        
    #include
        
         
    using namespace std;
    
    const int maxn=20000+10;
    int v,n;
    int a[32],f[maxn];//aÎªÃ¿¸öÎïÆ·µÄÌå»ý£¬fÎªµ±Ç°Ìå»ýÔÚÇ°i¸öÎïÆ·¿ÉÑ¡Ê±×î´óÌå»ý  ¼´ÔÀ´µÄf[i][v]  
    
    int main()
    {
    	scanf("%d%d",&v,&n);
    	for (int i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    	for (int i=1;i<=n;i++)
        {
            for (int j=v;j>=a[i];j--)
            {
                f[j]=max(f[j],f[j-a[i]]+a[i]); 
            }
        } 
        printf("%d\n",v-f[v]);
        return 0; 
    }

入了很多书，很多都要看，但更重要的还是好好学习好好写作业刷题。  
上上次在诸城一中还是漏了一句诗，那么这次两句  
——山外青山楼外楼，西湖歌舞几时休？  
——似此星辰非昨夜，为谁风露立中宵