背包九讲总结

最新推荐文章于 2018-01-22 10:45:39 发布

_zidaoziyan

最新推荐文章于 2018-01-22 10:45:39 发布

阅读量329

点赞数

分类专栏： dp

本文链接：https://blog.csdn.net/acm_fighting/article/details/52049023

版权

dp 专栏收录该内容

18 篇文章

订阅专栏

原文的链接http://wenku.baidu.com/link?url=kn8_h-XWMhXOsUsE2ZCfhRNZ1vzS8FyHs33y9GyE9wavno8OA9lRYMnmtB1wvLWPebvl0G856sCbVRQcI_m2Hn63DOPPGwW3rG5LzovKZCm

下面是自己的一些总结
1.多种背包的解法
一是二进制的拆分,容易写
二是用单调队列维护,实现O(VN)的时间复杂度
例如Hdu 2844
题意:给你一些不同价值和一定数量的硬币，求用这些硬币可以组合成价值在[1 , m]之间的有多少。

/*
Hdu 2844
题意:给你一些不同价值和一定数量的硬币，求用这些硬币可以组合成价值在[1 , m]之间的有多少。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int num[maxn],cnt[maxn],dp[110000];
struct node{
    int id,num;
}q[110000];

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0)
            break;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)   //表示每件物品的价值
            scanf("%d",&num[i]);
        for(int i=1;i<=n;i++)   //表示每件物品的数目
            scanf("%d",&cnt[i]);
        dp[0]=1;
        for(int i=1;i<=n;i++){  //特判为哪种类型的背包
            if(cnt[i]==1){  //为01背包
                for(int j=m;j>=num[i];j--)
                    dp[j]=max(dp[j],dp[j-num[i]]);
                continue;
            }
            if(cnt[i]*num[i]>=m){   //为多重背包,这一步一定要加
                for(int j=num[i];j<=m;j++)
                    dp[j]=max(dp[j],dp[j-num[i]]);
                continue;
            }
            /*
            若当前在尝试第i种硬币，那么dp[i]可以出现的情况就是存在一个j
            dp[j]=1&&(i-j)%a[i]==0&&(i-j)/a[i]<=c[i]
            又因为cnt[i]*num[i]<m所以时间复杂度一定小于等于n*m*/
            for(int j=0;j<num[i];j++){//余数为多少
                int head=0,tail=0;
                for(int v=0;v*num[i]+j<=m;v++){ //v表示用了多少个num[i]
                    while(tail>head&&dp[v*num[i]+j]>=q[head].num)
                        head++;
                    q[tail].num=dp[v*num[i]+j],q[tail++].id=v;
                    while(q[tail-1].id-q[head].id>cnt[i])   //注意等号不能取到
                        head++;
                    dp[v*num[i]+j]=max(dp[v*num[i]+j],q[head].num);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=m;i++)
            ans+=dp[i];
        printf("%d\n",ans);
    }
    return 0;
}

2.二维费用的背包问题
二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必
须同时付出这两种费用。对于每种费用都有一个可付出的最大值（背包容量）。问怎样
选择物品可以得到最大的价值。
设第 i 件物品所需的两种费用分别为 Ci 和 Di。两种费用可付出的最大值（也即两
种背包容量）分别为 V 和 U。物品的价值为 Wi。

思路:将数组拓展一维,dp[V][U]
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取 U 件物品。
这事实上相当于每件物品多了一种“件数”的费用，每个物品的件数费用均为 1，可以付出的最大件数费用为 U。

3.背包的分组问题
有N件物品和一个容量为V的背包。第i件物品的费用为ci,价值为wi,这些物品被分为K组,每组中的物品相互冲突,最多选一件。

for(k=1;k<=K;k++)
    for(v=V;v>=0；v--)
        for(all item i in k)
            dp[v]=max(dp[v],dp[V-c[i]]+w[i])

4.有依赖的树形dp

Hdu 1561
ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？(1 <= M <= N <= 200)

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
vector<int>G[202];
int dp[202][202];
int value[202],son[202];
int n,m;

void dfs(int u){
    son[u]=1;
    dp[u][1]=value[u];
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        dfs(v);
        son[u]+=son[v];
        for(int j=min(m+1,son[u]);j>=2;j--)
            for(int k=min(son[v],j-1);k>=1;k--){
                if(dp[v][k]==-1||dp[u][j-k]==-1)
                    continue;
                dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
            }
    }
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0)
            break;
        for(int i=0;i<=n;i++)
            G[i].clear();
        int u;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&u,&value[i]);
            G[u].push_back(i);
        }
        memset(dp,-1,sizeof(dp));
        dfs(0);
        int ans=0;
        for(int i=1;i<=m+1;i++)
            ans=max(ans,dp[0][i]);
        printf("%d\n",ans);
    }
    return 0;
}

ACdream 1032
题意:一棵树,任意选择相连的i个点,求最小值

/*
时间复杂度为O(n^2)
dp的含义:如果下方的节点要继续往上连接其他节点,那么它的父亲节点是必取的
*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=2100;
vector<int>G[maxn];
int a[maxn],ans[maxn],son[maxn],n;
int dp[maxn][maxn];

void dfs(int u,int pre){
    memset(dp[u],INF,sizeof(dp[u]));
    dp[u][1]=a[u];
    son[u]=1;
    for(int k=0;k<G[u].size();k++){
        int v=G[u][k];
        if(v==pre)
            continue;
        dfs(v,u);
        son[u]+=son[v];
        for(int j=son[u];j>=2;j--)
            for(int k=min(son[v],j-1);k>=1;k--)
                dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
    }
    for(int i=0;i<=n;i++)
        ans[i]=min(ans[i],dp[u][i]);
}

int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<=n;i++)
            G[i].clear();
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int u,v;
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        memset(ans,INF,sizeof(ans));
        dfs(1,-1);
        for(int i=1;i<=n;i++){
            if(i!=n)
                printf("%d ",ans[i]);
            else
                printf("%d\n",ans[i]);
        }
    }
    return 0;
}