关于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];
}
#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-08 12:45
吉林大学 硬件开发 现在深挖技术还来得及:大厂
我这个地方基本部门组里就我一个 同事要不出差 要不就是另一个地方办公
实习搭子来的第二周就去上海出差了,到现在还没回来
点赞 评论 收藏
分享
昨天 13:36
门头沟学院 Java 点赞 评论 收藏
分享
06-16 19:09
河南开封科技传媒学院 Java 
点赞 评论 收藏
分享