头像

Immerse




离线:9小时前


最近来访(2)
用户头像
RyanMoriarty

活动打卡代码 AcWing 1020. 潜水员

Immerse
18小时前

体积恰好是v

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 85;

int n, m, t;

int v1[N], v2[N], w[N];
int f[M][M];
int main(){
    //第一维费用大于等于i,第二维费用大于等于j的最小重量
    cin>>m>>n>>t;
    memset(f, 0x3f, sizeof f);
    f[0][0]=0;
    for(int i=1;i<=t;i++) cin>>v1[i]>>v2[i]>>w[i];
    for(int i=1;i<=t;i++){
        for(int j=m;j>=0;j--){
            for(int k=n;k>=0;k--){
                f[j][k]=min(f[j][k],f[max(j-v1[i],0)][max(k-v2[i],0)]+w[i]);//
                /*
                1.体积恰好是v
                     dp[0][0]初始化为0, 其他全部初始化为inf,同时也要严格保证任意状态下背包体积 >= 0
                    3.体积至少是v
                    dp[0][0]初始化为0, 其他全部初始化为inf, 任意状态下背包的体积允许 < 0
                */
            }
        }

    }
    cout<<f[m][n];
}



Immerse
21小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int f[1050][1100];
int v1[5500],v2[1010],w[1010];
int n,v,m;
int main(){
    cin>>n>>v>>m;
    for(int i=1;i<=n;i++) cin>>v1[i]>>v2[i]>>w[i];

    for(int i=1;i<=n;i++){
        for(int j=v;j>=v1[i];j--){//v1
            for(int t=m;t>=v2[i];t--){//v2

                f[j][t]=max(f[j][t],f[j-v1[i]][t-v2[i]]+w[i]);

            }

        }

    }

    cout<<f[v][m]<<" ";


}





Immerse
21小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int f[1050][1100];
int v1[5500],v2[1010];
int n,m,k;
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++) cin>>v1[i]>>v2[i];

    for(int i=1;i<=k;i++){
        for(int j=n;j>=v1[i];j--){//v1
            for(int t=m;t>=v2[i];t--){//v2

                f[j][t]=max(f[j][t],f[j-v1[i]][t-v2[i]]+1);

            }

        }

    }
    int res=m;
    cout<<f[n][m-1]<<" ";
    for(int i=0;i<=m-1;i++){
        if(f[n][m-1]==f[n][i])  res=min(res,i);

    }
    cout<<m-res<<endl;

}


活动打卡代码 AcWing 1024. 装箱问题

Immerse
22小时前
#include<iostream>
#include<algorithm>
using namespace std;
const int N =101000;
int f[N];
int v[N];
int n,m;

int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];

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

           f[j]=max(f[j],f[j-v[i]]+v[i]);
        }

    }
    cout<<m-f[m]<<endl;

}


活动打卡代码 AcWing 423. 采药

Immerse
22小时前
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
int f[N];
int v[N];
int w[N];
int n,m;

int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];

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

           f[j]=max(f[j],f[j-v[i]]+w[i]);
        }

    }
    cout<<f[m]<<endl;

}


活动打卡代码 AcWing 5. 多重背包问题 II

Immerse
22小时前
#include<iostream>
using namespace std;
const int N = 12010, M = 2010;
int n,m;
int v[N],w[N],s[N];
int f[M];
int main(){

    int a,b,s;
    cin>>n>>m;
    int cnt=0;

    //将数量为 s的物体,扩展为 1个,2个,4个....的物体,作为一个新的背包问题解决
    for(int i=1;i<=n;i++){
        cin>>a>>b>>s;
        int k=1;//组别里的个数?
        while(k<=s){
            cnt++;
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2; // 组别里的个数增加
        }
        if(s){
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
//    相当于把背包分组

    n=cnt;
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0&&j-v[i]>=0;j--){

            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }

    }
    cout<<f[m]<<endl;
}


活动打卡代码 AcWing 4. 多重背包问题

Immerse
23小时前
#include<iostream>
using namespace std;
const int N = 110;//朴素版本
int f[N][N];
int v[N],w[N],s[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];

    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            for(int k=0;k<=s[i];k++){
                if(j-k*v[i]>=0)
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

            }

        }
    }

    cout<<f[n][m]<<endl;

}


活动打卡代码 AcWing 3. 完全背包问题

Immerse
23小时前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N][N];
int n,m;
int v[N],w[N];//体积 价值
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=f[i-1][j];
            if(j-v[i]>=0) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);

        }


    }
    cout<<f[n][m]<<endl;

}


活动打卡代码 AcWing 2. 01背包问题

Immerse
23小时前
#include<iostream>
#include<algorithm>
using namespace std;
const int N =1010;
int f[N];
int v[N];
int w[N];
int n,m;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i];

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

           f[j]=max(f[j],f[j-v[i]]+w[i]);
        }

    }
    cout<<f[m]<<endl;

}



Immerse
2天前

优化前

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);

for (int i = 1; i <= n; i ++ )
{
    for (int j = 1; j <= n; j ++ )
    {

        f[i][j] = f[i - 1][j];

        if (a[i] == b[j])
        {
            int maxv = 1;//初始化包括空集情况
            for (int k = 1; k < j; k ++ )//本循环还有限制b[k]在前j-1的作用
                if (a[i] > b[k])
                    maxv = max(maxv, f[i - 1][k] + 1);


            f[i][j] = max(f[i][j], maxv);
        }
    }
}


    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
    printf("%d\n", res);

    return 0;
}



对其做等价变换
``
scanf(“%d”, &n);
for (int i = 1; i <= n; i ) scanf(“%d”, &a[i]);
for (int i = 1; i <= n; i
) scanf(“%d”, &b[i]);

for (int i = 1; i <= n; i ++ )
{
    int maxv = 1;//表示1~j-1的
    for (int j = 1; j <= n; j ++ )
    {
        f[i][j] = f[i - 1][j];
        if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);

        if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        //因为要保持的是公共上升的最大值,除了相等还要维护上升这个性质
    }
}

int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
printf("%d\n", res);

return 0;

``