背包DP

· · 个人记录

背包DP

背包问题的特性：存在一定的属性限制，对应物品具有该限制属性，求解在限制条件下的最有价值/方案总数

01背包

每个物品有且只有一个
dp[物品][限制条件] 在前i个物品中挑选若干个，在限制为j的情况下的最优价值
滚动数组
1.两者时间复杂度相同，滚动数组空间大大减少
2.滚动数组覆盖，丢失了中间状态的信息
空间要求比较严格，最后不需要中间状态信息

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

完全背包

每种物品有无限个。dp[i][j]前i种物品挑选若干件，在空间限制为j下的最优价值

精卫填海

目的：判断是否可以填平，能则输出剩余最大体力，否则输出impossible
总体力-耗费体力=剩余体力 概括：有体力限制下求解最大的填埋体积，木石只能使用一次。定位算法01背包

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=10010;
int k[N],m[N],dp[N];
int v,n,c;
int main(int argc,char *argv[]){
    scanf("%d%d%d",&v,&n,&c);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&k[i],&m[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=c;j>=m[i];j--){
            dp[j]=max(dp[j],dp[j-m[i]]+k[i]);   
        }
    } 
    if(dp[c]<v){
        printf("impossible");
    }
    else{
        for(int j=0;j<=c;j++){
            if(dp[j]>=v){
                printf("%d",c-j);
                break;
            }
        }
    }
    return 0;
}

音量调节

目的：求出演奏最后一首歌时的最大音量，无法演奏输出-1
影响演奏音量的行为：可以选择调高、调低 音量c[i]
概括：在音量限制下能够到达的最大音量。
限制 最优 两种选择 -> 01背包
当前到达音量为x 前一首歌的音量 x+c[i]（调低了变成x） x-c[i]（调高了变成x）
设定dp[i][j] 演奏第i首歌时，音量j是否可以到达 (bool类型) 

dp[i][j]=dp[i-1][j+c[i]]||dp[i-1][j-c[i]]

垃圾陷阱

目的：判断能否爬出，能输出最早爬出的时间，不能则输出最长的存活时间
爬出的条件：堆放高度>=深度D 隐藏条件：存活时间足够
最长的存活时间。
处理垃圾 1.吃掉垃圾。存活时间增长，高度不变。
2.堆放垃圾。高度增加，存活时间不变。
最长：每个垃圾都选择吃掉。
部分分思路：每个垃圾都选择吃掉。 先对垃圾按时间顺序排序。每落下一个垃圾选择吃掉。过程中扣除等待消耗的存活时间。

sort();
for*(int i=1;i<=n;i++){//遍历所有垃圾
    int fab=a[i].t-a[i-1].t;
   re-=fab;
   if(re<0) break;
   re+=fab;
   maxT+=fab;
}

部分分代码

#include<stdio.h>
#include<algorithm> 
using namespace std;
int D,G;
struct node{
    int t,f,h;
}a[105];
bool cmp(node A,node B){
    return A.t<B.t;
}
int main(int argc,char *argv[]){
    int re=10,maxT=10;
    scanf("%d%d",&D,&G);
    for(int i=1;i<=G;i++){
        scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);
    }
    sort(a+1,a+G+1,cmp);
    for(int i=1;i<=G;i++){
        int fab=a[i].t-a[i-1].t;
        re-=fab;
        if(re<0){
            break;
        }
        re+=a[i].f;
        maxT+=a[i].f;
    }
    printf("%d",maxT);
    return 0;
}

当垃圾到达之后，就决定垃圾的处理方式，不再发生变化 

dp[i][j]=max(dp[i][j],dp[i-1][j+fab]+a[i].h)
dp[i][j+a[i].f]=max( ,dp[i-1][j+fab])
vis[0][10]=1;
for(int i=1;i<=G;i++){
    for(int j=maxT;j>=0;j--){
        if(vis[i-1]j+fab]){//上个阶段存货
          //1.选择堆放垃圾
          dp[i][j]=
          vis[i][j]=1;
          //2.选择吃掉垃圾
          dp[i][j+a[i].f]=xxx;
          vis[i][j+a[i].f]=1;
        }
        if(dp[i][j]>=D){
            cout<<a[i].t;
            return 0;
        }
    }
}
cout<<maxT;

code 

#include<stdio.h>
#include<algorithm> 
using namespace std;
int D,G;
struct node{
    int t,f,h;
}a[105];
bool cmp(node A,node B){
    return A.t<B.t;
}
int dp[105][4005]; 
bool vis[105][4005];
int main(int argc,char *argv[]){
    int re=10,maxT=10;
    scanf("%d%d",&D,&G);
    for(int i=1;i<=G;i++){
        scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);
    }
    sort(a+1,a+G+1,cmp);
    for(int i=1;i<=G;i++){
        int fab=a[i].t-a[i-1].t;
        re-=fab;
        if(re<0){
            break;
        }
        re+=a[i].f;
        maxT+=a[i].f;
    }
    //更新
    vis[0][10]=1;
    for(int i=1;i<=G;i++){
        int fab=a[i].t-a[i-1].t;
        for(int j=maxT;j>=0;j--){
            if(vis[i-1][j+fab]){
                dp[i][j]=max(dp[i][j],dp[i-1][j+fab]+a[i].h);
                vis[i][j]=1;
                dp[i][j+a[i].f]=max(dp[i][j+a[i].f],dp[i-1][j+fab]);
                vis[i][j+a[i].f]=1;
            }
            if(dp[i][j]>=D){
                printf("%d",a[i].t);
                return 0;
            }
        }
    } 
    printf("%d",maxT);
    return 0;
}