关于01背包问题和完全背包的板子与区别

(1)01背包
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e7;
int dp[105][1005];
signed main()
{
std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    int n,t;
    cin>>n>>t;
    int w[n+1],v[n+1];
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=t;j++)
        {
            if(j>=w[i])
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);这一行不同
            else
                dp[i][j]=dp[i-1][j];
        }
    cout<<dp[n][t];
return  0;
}
(2)完全背包
for(int i=1;i<=n;i++)
        for(int j=1;j<=t;j++)
        {
            if(j>=w[i])
            dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);这一行不同,可以取多个
            else
                dp[i][j]=dp[i-1][j];
        }
全部评论

相关推荐

码农索隆:1.照片换成证件照。 2.专业技能写的太少了,太单薄了。 3.项目经历描写的太冗余,分成几点。 4.无实习经历,看看能不能包一个。
点赞 评论 收藏
分享
驼瑞驰_招募评论官版...:把对方打入公司库是吧
点赞 评论 收藏
分享
今天刚通知oc
跑不快的yyyf:接好运
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务