8 条题解

  • 2
    @ 2023-8-6 10:45:52
    #include <cmath>
    #include <cstring>
    #include <string.h>
    #include <queue>
    #include <stack>
    #include <map>
    using namespace std;
    const int N = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int n,m;
    int w[N],v[N],dp[205];
    int main(){
    	cin >> m >> n;
    	for(int i=1; i<=n; i++)
    	    cin >> w[i] >> v[i];
    	for(int i= 1; i<=n; i++){
    		for(int j=m; j>=w[i]; j--){
    			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    		}
    	}
    	cout << dp[m]; 
    	return 0;
    }
    //01背包0一维数组优解,制作不易,点个赞再走吧
    
  • 1
    @ 2023-9-24 15:48:05

    #include <iostream> using namespace std; struct node{ int price; int time; bool flag; } a[100005]; int n, ans, l, r; int main(){ cin >> n; l = 1; for(int i = 1;i <= n;i ++) { int x, p, t; cin >> x >> p >> t; if(x == 0) { a[++r].price = p; a[r].time = t; ans += p; } else { for(int i = l;i <= r;i ++) { if(t - a[i].time > 45) { l ++; continue; } if(a[i].price >= p && a[i].flag == 0) { a[i].flag = 1; ans -= p; break; } } ans += p; } } cout << ans; return 0; }

    • 0
      #include<bits/stdc++.h>
      #pragma GCC optimize(3)
      #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      using namespace std;
      const int N=310;
      const int INF=0x3f3f3f3f;
      int dp[N][N],n,m,w[N],c[N]; 
      int main()
      {
      	IOS;
      	cin>>m>>n;
      	for(int i=1;i<=n;++i)
      	{
      		cin>>w[i]>>c[i];
      	}
      	for(int i=1;i<=n;++i)
      	{
      		for(int v=m;v>0;--v)
      		{
      			if(v>=w[i])
      			    dp[i][v]=max(dp[i-1][v],(dp[i-1][v-w[i]]+c[i]));
      			else
      			    dp[i][v]=dp[i-1][v];
      		}
      	}
      	cout<<dp[n][m];
          return 0;
      }
      
      
      • 0
        @ 2023-9-24 15:44:21

        P1725 0/1背包问题

        本人以坑人乐于助人为主

        本代码是有很多bug没有注释的

        现在我要删掉分享我的代码

        这是TeMeGe链接http://luogu.com

        这是洛谷链接http://temege.com

        现在打出我的真代码

        元神,启动
        

        搞错了

        #include
        using namespace std;
        int W[1010],V[1010];
        int dp[1010][1010];
        int m,n; 
        int main()
        {
        	cin>>m>>n;
        	for(int i=1;i<=n;i++)cin>>W[i]>>V[i]; 
        	for(int i=1;i<=n;i++){
        		for(int j=1;j<=m;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][m];
        }
        
        • -2
          @ 2023-4-9 15:49:11

          P1725 0/1背包问题

          背包DP模板题,这个屑蒟蒻并没有压缩状态

          注释在CODE挺详细的了

          CODE

          #include<bits/stdc++.h>
          using namespace std;
          int W[1010],V[1010];
          int dp[1010][1010];//dp[前x件物品][已用重量]=对应最大价值 
          int m,n; 
          int main()
          {
          	cin>>m>>n;
          	for(int i=1;i<=n;i++)cin>>W[i]>>V[i]; 
          	for(int i=1;i<=n;i++){//枚举第i件物品 
          		for(int j=1;j<=m;j++){//插入第i件物品后重量 
          			if(j>=W[i]){//插入后重量肯定得比该物件要重吧…… 
          				dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]);
          				//dp[i-1][j] 即为 不选该物件,不选且重量达到j的最优价值 
          				//dp[i-1][j-W[i]]+V[i] 即为 选择该物件,那么,可以得出,在没有选择该物件时,重量为j-W[i] 
          				//故在该状态+V[i](对应物品的价格) 
          			}
          			else{
          				dp[i][j]=dp[i-1][j];//见上 
          			}
          		}
          	} 
          	cout<<dp[n][m];//输出最优结果 
          }
          
          • -2

            #include <iostream> using namespace std; int c[10001],w[10001],dp[10001]; int main(){ int m,n; cin>>m>>n; for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; } for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+c[i]); cout<<dp[m]; }

            • -3

              P1725 0/1背包问题

              本人的第n篇题解

              这题很简单,用dfs就搞定了!

              代码:

              #include<iostream>
              using namespace std;
              int m,n,sumw,sumc,maxnc;//sumw:用来记录重量的总和,sumc:用来记录价值的总和,maxnc:用来记录最大的总和 
              bool b[1000000]={0};
              struct s{
              	int w,c;//w表示重量,c表示价值 
              } a[1000000]={0};
              void dfs(int x){
              	for(int i=x;i<=n;i++){
              		if(sumw+a[i].w<=m&&b[i]==0){//判断sumw+这个魔法石的重量会不会超出背包重量,还要判断有没有算过 
              			sumw+=a[i].w;//加上重量 
              			sumc+=a[i].c;//加上价值 
              			b[i]=1;//算过了 
              			dfs(i);
              			b[i]=0;//还原 
              			sumw-=a[i].w;
              			sumc-=a[i].c;
              		} 
              	}
              	maxnc=max(sumc,maxnc);//比较最大的 
              	return;
              }
              int main(){
              	cin>>m>>n; 
              	for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].c;//输入数字 
              	dfs(1);
              	cout<<maxnc;//输出 
              	return 0;
              }
              

              制作不易,点个赞再走吧。

              • 1

              信息

              ID
              1725
              时间
              1000ms
              内存
              256MiB
              难度
              5
              标签
              递交数
              219
              已通过
              79
              上传者