POJ3628-Bookshelf 2-DP，0-1双肩包

POJ3628-Bookshelf 2-DP，0-1背包

方法一：最朴素方法，不优化时间和空间

空间和时间复杂度都是O(n*s)，n为奶牛数目，s为奶牛高度之和

?

代码：照理说，空间复杂度超过限制，但是POJ居然通过了

#include <stdio.h>#include <stdlib.h>#include <iostream>using namespace std;int n;int b;int h[21];int s;//DPbool dp[20000001];     //dp[21][20000001]//DP(0-1背包) void solve(){     //DP(0-1背包) init     int i,j;     dp[0]=true;     for(j=1;j<=s;j++)         dp[j]=false;              //DP(0-1背包)     for(i=1;i<=n;i++){         for(j=s;j>=0;j--){               //dp[j]=dp[j];               if(j-h[i]>=0){                   dp[j]=dp[j] || dp[j-h[i]];               }           }       }}int main(){    //input    scanf("%d%d",&n,&b);    int i;    s=0;    for(i=1;i<=n;i++){        scanf("%d",&h[i]);        s+=h[i];    }        //DP(0-1背包)     solve();        //output    for(i=b;i<=s;i++){        if(dp[i]==true){  //if(dp[n][i]==true){            printf("%d\n",i-b);            break;        }    }        system("pause");    return 0;}

?