11-26 21:25 哈尔滨理工大学 发布于黑龙江
关注
关于01背包问题和完全背包的板子与区别
(1)01背包
#include
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<
}
(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
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<
}
(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];
}
全部评论
相关推荐
