DP-01背包

好的  md这个编译器怎么用啊

好吧  今天复习了01背包 在不写下来就又忘了。。。。

 

果然嗷,《挑战程序设计竞赛》关于背包的引入我看的很棒,先记下来

 

最朴素的方法:
针对每个物品是否放入背包进行搜索试试看

int n,m;
int weight[MAX],val[MAX];

int rec(int i,int j)//从第i个物品挑选总重小于j的部分 
{
    int res;
    if(i==n) res=0;//已经没有剩余物体了 
    else if(weight[i]>j) res=rec(i+1,j);//选不了 
    else res=max(rec[i+1][j],rec[i+1][j-weight[i]]+val[i]);//要么选or不选 
    return res;
}

void solve()
{
    printf("%d\n",rec(1,m));
}

 

最坏是O(2n);

递归的调用

 

然后可以用一个数组(二维)存放已经算过的,之后直接调用即可

不用函数,利用递推式,简单的二重循环

for(int i=n;i>=1;i--){
        for(int j=0;j<=m;j++){
            if(weight[i]>j) dp[i][j]=dp[i+1][j];
            else dp[i][j]=max(dp[i+1][j],dp[i+1][j-weight[i]]+val[i]);
        }
    }
    printf("%d",dp[1][m]);

滚动数组

for(int i=n;i>=1;i--){
        int res=i%2;
        int deta=(res%2==1)?-1:1;
        for(int j=0;j<=m;j++){
            if(weight[i]>j) dp[res][j]=dp[res+deta][j];
            else dp[res][j]=max(dp[res+deta][j],dp[res+deta][j-weight[i]]+val[i]);
        }
    }
    printf("%d",dp[1][m]);

没找到题目来测试,估计应该没有问题

 

 

明天的话,打算把怎么选的路径给学会,和一些经典DP像LCS啊之类的,

这样写太累了而且感觉没有效果,以后只写我难理解的,剩下的时间感觉可以拿去做题

 

希望有用吧,就算用这个时间去学常规,估计我也学不进去。

 

上一篇:【Leetcode】312 戳气球


下一篇:1115 Counting Nodes in a BST