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

相关推荐

07-15 11:41
门头沟学院 Java
点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
07-02 10:39
门头沟学院 Java
Steven267:说点真实的,都要秋招了,还没有实习,早干嘛去了,本来学历就差,现在知道急了,而且你这个简历完全可以写成一页,劣势太大了,建议转测试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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