开门见山 ╰(*°▽°*)╯

我P某人要开讲了~

 

dp[n][v]状态定义为：选择前n个物品的若干个装入体积为v的包中 ，所能获得的最大价值


那么有对于当前的状态，我们有 dp[n][v]=max(dp[n-1][v],dp[n-1][v-w[n]]+v[n]]   


接下来叙述一个问题 ：   01背包恰好装满 与 不要求恰好装满

1.若为恰好装满

要恰好装满，对于dp数组的初始化有所不同，很显然有些状态不能恰好装满，其中有dp[0][1~v]=dp[1~n][0]-无穷 dp[0][0]=0 再进行DP。 NOW只求会用，想知道证明原理的可以到百度上搜索


2.无需恰好装满

无需恰好装满，memset(dp,0,sizeof(dp))  就哦开la ~  (๑•̀ㅂ•́)و✧ !!!


再叙述一个问题：01背包时间与空间优化问题

1.空间优化

for(int i=1;i<=n;i++){
            for(int j=m;j>=1;j--){
               if(j>=w[i])  dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }

2.时间优化

初级优化

for(int i=1;i<=n;i++){
            for(int j=m;j>=w[i];j--){
               dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
高级常数优化 

for(int i=1;i<=n;i++){
            if(i>1) sum-=w[i-1];
            int lim=max(n-sum,w[i]);
            for(int j=m;j>=lim;j--){
               dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }


欧凯·-· 就这么多！

2018.1.19 凌晨1：07

晚上睡不着觉，打开BLOG开始学习

输出DP路径

void traceback(){ for(int i=n;i>1;i--){ if(m[i][c]==m[i-1][c]) x[i]=0; else{ x[i]=1; c-=w[i]; } } x[1]=(m[1][c]>0)?1:0; }