【Luogu P1048 Luogu P1016】采药/疯狂的采药

采药/疯狂的采药

两道模板题，分别是0-1背包和完全背包。

0-1背包

二维：dp[i][j]=max(dp[i-1][j-time[i]]+v[i],dp[i-1][j]);

由于i的状态由i-1的状态转移而来，那么可以省去物品的维度。

但是重量/容积维度的循环j必须倒序进行，否则可能使物品被重复选。

大家可以自己思考一下为什么。

一维：dp[j]=max(dp[j-time[i]]+v[i],dp[j]);

#include<iostream>

#include<cstdio>

using namespace std;

int dp[1001][1001],t,m,time[1001],v[1001];

int main()

{

    cin>>t>>m;

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

    for (int i=1;i<=t;i++) dp[0][i]=0;

    for (int i=1;i<=m;i++)

        for (int j=t;j>=0;j--)

            if (j>=time[i]) dp[i][j]=max(dp[i-1][j-time[i]]+v[i],dp[i-1][j]);

            else dp[i][j]=dp[i-1][j];

    cout<<dp[m][t];

    return 0;

}

二维0-1背包做法程序参考

#include<iostream>

#include<cstdio>

using namespace std;

int dp[1001],t,m,time[1001],v[1001],max1;

int main()

{

    cin>>t>>m;

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

    for (int i=1;i<=m;i++)

        for (int j=t;j>=time[i];j--)

            dp[j]=max(dp[j-time[i]]+v[i],dp[j]);

    cout<<dp[t];

    return 0;

}

一维0-1背包做法程序参考

完全背包

在0-1背包中的重量/容积维度倒序循环是为了防止物品被重复选。那么其实直接将其改成顺序循环即可。

当然也可以加多一重循环，枚举物品选用的个数，但是这个做法会TLE。

#include<iostream>

#include<cstdio>

using namespace std;

int dp[100001],t,m,time[100001],v[10001];

int main()

{

    cin>>t>>m;

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

    for (int i=1;i<=t;i++) dp[i]=0;

    for (int i=1;i<=m;i++)

        for (int j=time[i];j<=t;j++)

             dp[j]=max(dp[j-time[i]]+v[i],dp[j]);

    cout<<dp[t];

    return 0;

}

完全背包程序参考

巴特西

【Luogu P1048 Luogu P1016】采药/疯狂的采药

0-1背包

完全背包

最新文章

热门文章