关于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];
        }
全部评论

相关推荐

05-19 15:21
已编辑
华南农业大学 Java
白火同学:你才沟通了200,说实话,北上广深杭这里面你连一座城市的互联网公司都没投满呢,更别说还有各种准一线二线城市了。等你沟通突破了三位数,还没结果再考虑转行的事吧。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 14:23
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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