当前位置：首页 > ops >正文

C++动态规划-01背包

ops 2025/6/24 19:47:31

采药

#include <bits/stdc++.h>
using namespace std;
int t,m;//T:总时间 m:物品数数量
int dp[1005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t>>m;for(int i=1; i<=m; i++){int w,v;cin>>w>>v;for(int j=t; j>=w; j--) dp[j]=max(dp[j],dp[j-w]+v);}cout<<dp[t];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int t,m;//T:总时间 m:物品数数量
int dp[1005];
int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin>>t>>m;
   for(int i=1; i<=m; i++)
   {
       int w,v;
       cin>>w>>v;
       for(int j=t; j>=w; j--) dp[j]=max(dp[j],dp[j-w]+v);
   }
   cout<<dp[t];
   return 0;
}
开心的金明

#include <bits/stdc++.h>
using namespace std;
int t,m;
int dp[100005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t>>m;for(int i=1; i<=m; i++){int money,zh;cin>>money>>zh;int w=money,v=money*zh;for(int j=t; j>=w; j--) dp[j]=max(dp[j],dp[j-w]+v);}cout<<dp[t];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int t,m;
int dp[100005];
int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin>>t>>m;
   for(int i=1; i<=m; i++)
   {
       int money,zh;
       cin>>money>>zh;
       int w=money,v=money*zh;
       for(int j=t; j>=w; j--) dp[j]=max(dp[j],dp[j-w]+v);
   }
   cout<<dp[t];
   return 0;
}
花园采药

#include <bits/stdc++.h>
using namespace std;
int T;
int n,m;
int dp[10005];
int v[205],w[205];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;for(int k=1; k<=T; k++){cin>>n>>m;memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++) cin>>v[i];for(int i=1; i<=n; i++){cin>>w[i];for(int j=m; j>=w[i]; j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}//for(int i=1; i<=m; i++) cout<<dp[i]<<" ";//cout<<'\n'; cout<<dp[m]<<'\n';}return 0;
}
/*
2
5 10
1 2 3 4 5
5 4 3 2 1
5 10
1 2 3 4 5
5 1 5 4 3*/

#include <bits/stdc++.h>
using namespace std;
int T;
int n,m;
int dp[10005];
int v[205],w[205];
int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin>>T;
   for(int k=1; k<=T; k++)
   {
       cin>>n>>m;
       memset(dp,0,sizeof(dp));
       for(int i=1; i<=n; i++) cin>>v[i];
       for(int i=1; i<=n; i++)
       {
           cin>>w[i];
           for(int j=m; j>=w[i]; j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
       }
       //for(int i=1; i<=m; i++) cout<<dp[i]<<" ";
       //cout<<'\n';
       cout<<dp[m]<<'\n';
   }
   return 0;
}
/*
2
5 10
1 2 3 4 5
5 4 3 2 1
5 10
1 2 3 4 5
5 1 5 4 3

装箱问题

#include <bits/stdc++.h>
using namespace std;
int n,m;
int dp[100005];
int v[205],w[205];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>m>>n;for(int i=1; i<=n; i++){cin>>w[i];for(int j=m; j>=w[i]; j--) dp[j]=max(dp[j],dp[j-w[i]]+w[i]);}//for(int i=1; i<=m; i++) cout<<dp[i]<<" ";//cout<<'\n'; cout<<m-dp[m]<<'\n';return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m;
int dp[100005];
int v[205],w[205];
int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin>>m>>n;
   for(int i=1; i<=n; i++)
   {
       cin>>w[i];
       for(int j=m; j>=w[i]; j--) dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
   }
   //for(int i=1; i<=m; i++) cout<<dp[i]<<" ";
   //cout<<'\n';
   cout<<m-dp[m]<<'\n';
   return 0;
}

数字组合

#include <bits/stdc++.h> 
using namespace std;
int n,m; 
int a[105];
int dp[10005];
int main()
{cin>>n>>m;for(int i=1; i<=n; i++) cin>>a[i];dp[0]=1;for(int i=1; i<=n; i++){int now=a[i];for(int j=m; j>=now; j--) dp[j]+=dp[j-now];}
//	for(int i=1; i<=m; i++) cout<<dp[i]<<" ";
//	cout<<'\n';cout<<dp[m];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[105];
int dp[10005];
int main()
{
   cin>>n>>m;
   for(int i=1; i<=n; i++) cin>>a[i];
   dp[0]=1;
   for(int i=1; i<=n; i++)
   {
       int now=a[i];
       for(int j=m; j>=now; j--) dp[j]+=dp[j-now];
   }
//   for(int i=1; i<=m; i++) cout<<dp[i]<<" ";
//   cout<<'\n';
   cout<<dp[m];
   return 0;
}

淘淘的盒子

#include <bits/stdc++.h>
using namespace std;
int n,z;
int w[105][3];
int v[105][3];
int s[10005];
int t1[10005];
int t2[10005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>z;for(int i=1; i<=n; i++){cin>>w[i][1]>>v[i][1];cin>>w[i][2]>>v[i][2];for(int j=z; j>=w[i][1]; j--) t1[j]=max(s[j],s[j-w[i][1]]+v[i][1]);for(int j=z; j>=w[i][2]; j--) t2[j]=max(s[j],s[j-w[i][2]]+v[i][2]);for(int j=z; j>=min(w[i][1],w[i][2]); j--) s[j]=max(t1[j],t2[j]);}cout<<s[z];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,z;
int w[105][3];
int v[105][3];
int s[10005];
int t1[10005];
int t2[10005];
int main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin>>n>>z;
   for(int i=1; i<=n; i++)
   {
       cin>>w[i][1]>>v[i][1];
       cin>>w[i][2]>>v[i][2];
       for(int j=z; j>=w[i][1]; j--) t1[j]=max(s[j],s[j-w[i][1]]+v[i][1]);
       for(int j=z; j>=w[i][2]; j--) t2[j]=max(s[j],s[j-w[i][2]]+v[i][2]);
       for(int j=z; j>=min(w[i][1],w[i][2]); j--) s[j]=max(t1[j],t2[j]);
   }
   cout<<s[z];
   return 0;
}
金明的预算方案

#include<bits/stdc++.h>
using namespace std;
int n,m,v1,p1,q1;
int v[105][3],p[105][3];
int s[105][200005];
int main()
{cin>>n>>m;for(int i=1; i<=m; i++){cin>>v1>>p1>>q1;if(q1){if(v[q1][1]){v[q1][2]=v1;p[q1][2]=p1;}else{v[q1][1]=v1;p[q1][1]=p1;}}else{v[i][0]=v1;p[i][0]=p1;}}for(int i=1; i<=m; i++){for(int j=0; j<=n; j++){s[i][j]=s[i-1][j];if(v[i][0]<=j){int nee=v[i][0]*p[i][0];s[i][j]=max(s[i][j],s[i-1][j-v[i][0]]+nee);}if(v[i][0]+v[i][1]<=j){int ne1=v[i][1]*p[i][1];int ne2=v[i][0]*p[i][0];s[i][j]=max(s[i][j],s[i-1][j-v[i][0]-v[i][1]]+ne1+ne2);}if(v[i][0]+v[i][2]<=j){int ne1=v[i][2]*p[i][2];int ne2=v[i][0]*p[i][0];s[i][j]=max(s[i][j],s[i-1][j-v[i][0]-v[i][2]]+ne1+ne2);}if(v[i][0]+v[i][1]+v[i][2]<=j){int ne1=v[i][0]*p[i][0];int ne2=v[i][1]*p[i][1];int ne3=v[i][2]*p[i][2];s[i][j]=max(s[i][j],s[i-1][j-v[i][0]-v[i][1]-v[i][2]]+ne1+ne2+ne3);}}}cout<<s[m][n];return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,v1,p1,q1;
int v[105][3],p[105][3];
int s[105][200005];
int main()
{
   cin>>n>>m;
   for(int i=1; i<=m; i++)
   {
       cin>>v1>>p1>>q1;
       if(q1)
       {
           if(v[q1][1])
           {
               v[q1][2]=v1;
               p[q1][2]=p1;
           }
           else
           {
               v[q1][1]=v1;
               p[q1][1]=p1;
           }
       }
       else
       {
           v[i][0]=v1;
           p[i][0]=p1;
       }
   }
   for(int i=1; i<=m; i++)
   {
       for(int j=0; j<=n; j++)
       {
s[i][j]=s[i-1][j];
           if(v[i][0]<=j)
           {
               int nee=v[i][0]*p[i][0];
               s[i][j]=max(s[i][j],s[i-1][j-v[i][0]]+nee);
           }
           if(v[i][0]+v[i][1]<=j)
           {
               int ne1=v[i][1]*p[i][1];
               int ne2=v[i][0]*p[i][0];
               s[i][j]=max(s[i][j],s[i-1][j-v[i][0]-v[i][1]]+ne1+ne2);
           }
           if(v[i][0]+v[i][2]<=j)
           {
               int ne1=v[i][2]*p[i][2];
               int ne2=v[i][0]*p[i][0];
               s[i][j]=max(s[i][j],s[i-1][j-v[i][0]-v[i][2]]+ne1+ne2);
           }
           if(v[i][0]+v[i][1]+v[i][2]<=j)
           {
               int ne1=v[i][0]*p[i][0];
               int ne2=v[i][1]*p[i][1];
               int ne3=v[i][2]*p[i][2];
               s[i][j]=max(s[i][j],s[i-1][j-v[i][0]-v[i][1]-v[i][2]]+ne1+ne2+ne3);
           }
       }
   }
   cout<<s[m][n];
   return 0;
}