9 条题解

  • 1
    @ 2025-5-18 19:50:05
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1000+10;
    int m , w[N] , c[N] , dp[1010] , n;
    int main(){
    	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--)
            {
            	if(w[i] > j)
            	    dp[j] = dp[j];
            	else   
            	    dp[j] = max(dp[j] , dp[j - w[i]] + c[i]);
    		}
    	cout << dp[m];
    	return 0;
    }
    
    • 0
      @ 2025-6-22 20:05:20
      #include <bits/stdc++.h>
      using namespace std;
      const int N = 1e5 + 10;
      int t,m,w[N],c[N],dp[N][2000];
      int main(){
      	cin >> t >> m;
      	for(int i = 1;i <= m;i++){
      		cin >> w[i] >> c[i];
      	}
      	for(int i = 1;i <= m;i++){
      		for(int j = 1;j <= t;j++){
      			if(w[i] > j){
      				dp[i][j] = dp[i - 1][j];
      			}else{
      				dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + c[i]);
      			}
      		}
      	}
      	cout << dp[m][t];
      	return 0;
      }
      
      • 0
        @ 2025-5-18 18:16:27
        #include<bits/stdc++.h>
        using namespace std;
        
        const int N=1e3+10;
        int n,m,w[N],c[N],dp[N][N];
        
        int main(){
        	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=1;j<=m;j++){
        			if(w[i]>j)dp[i][j]=dp[i-1][j];
        			else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]); 
        		}
        	}
        	cout<<dp[n][m];
        	return 0;
        }
        
        
        
        • 0
          @ 2025-2-23 10:05:56
          #include<iostream>
          using namespace std;
          
          int dp[1100],v[1100],w[1100];
          
          int main(){
              int W,m;
              cin>>W>>m;
              for(int i = 1; i <= m; i++){
                  cin>>w[i]>>v[i];
              }
              for(int i = 1; i <= m; i++){
                  for(int j = W; j >= w[i]; j--){
                      dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
                  }
              }
              cout<<dp[W];
              return 0;
          }
          

          01背包模板

          • 0
            @ 2024-12-17 13:21:50
            #include <stdio.h>
            #include <iostream>
            using namespace std;
            inline int read(string n){
            	int x = 0, f = 1;
            	printf("%s", n.c_str());
            	char c = getchar();
            	while(c < '0'  ||  c > '9'){
            		if(c == '-')
            			f = -1;
            		c = getchar();
            	}
            	while(c >= '0'  &&  c <= '9'){
            		x = x * 10 + c - 48;
            		c = getchar();
            	}
            	return x * f;
            }
            inline float input(string n){
            	float x = 0, f = 1, x2 = 0, cnt = 0, i = 0;
            	printf("%s", n.c_str());
            	char c = getchar();
            	while(c < '0'  ||  c > '9'){
            		if(c == '-')
            			f = -1;
            		c = getchar();
            	}
            	while(c >= '0'  &&  c <= '9'){
            		x = x * 10 + c - 48;
            		c = getchar();
            	}
            	c = getchar();
            	while(c >= '0'  &&  c <= '9'){
            		x2 = x2 * 10 + c - 48;
            		cnt++;
            		c = getchar();
            	}
            	for(; i < cnt; i++)
            		x2 /= 10.0;
            	return (x + x2) * f;
            }
            void write(int n) {
                if(n < 0){
                    putchar('-');
                    n = -n;
                }
                if(n > 9)
            		write(n / 10);
                putchar(n % 10 + '0');
            	return;
            }
            void print(float n){
            	printf("%lf\n", n);
            	return;
            }
            int w[101], val[101];
            int dp[1001];
            int main(){
                int t = read(""), m = read(""), res = -1;
                for(int i=1;i<=m;i++)
                    w[i] = read(""), val[i] = read("");
                for(int i = 1; i <= m; i++) 
                	for(int j = t; j >= 0; j--) 
                        if(j >= w[i])
                            dp[j] = max(dp[j - w[i]] + val[i], dp[j]);
                write(dp[t]);
                return 0;
            }
            
            • -1
              @ 2023-9-2 21:02:56
              #include <iostream>
              using namespace std;
              const int M=1e3+10;
              const int N=1e2+10;
              int w[N],c[N],dp[M];
              int main(){
              	int t,n;
              	cin>>t>>n;
              	for(int i=1;i<=n;i++)cin>>w[i]>>c[i];
              	for(int i=1;i<=n;i++){
              		for(int j=t;j>=w[i];j--){
              			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
              		}
              	}
              	cout<<dp[t]<<endl;
              	return 0;
              }
              
              • -1
                @ 2023-4-22 9:48:22
                #include <bits/stdc++.h>
                #include<iostream>
                using namespace std;
                int f[10001];//状态函数f[j]表示第i件物品容量为j最大价值
                int v[10001]; 
                int w[10001];
                /*
                函数功能:求0-1背包问题的最大价值
                函数形参:物品数量和背包容量
                函数返回值:返回最大值 
                */   
                int fun(int n,int m)
                {
                	for(int i=1;i<=n;i++)
                	{
                		for(int j=m;j>=w[i];j--)//逆序 
                		{
                			f[j]=max(f[j],f[j-w[i]]+v[i]);
                		}
                	}
                		return f[m];
                }
                int main()
                {
                	int n,m;
                	cin>>m>>n;
                	for(int i=1;i<=n;i++)
                		cin>>w[i]>>v[i];
                	cout<<fun(n,m);
                	return 0;
                }
                
                • -1
                  @ 2021-10-6 19:48:35
                  
                  #include<bits/stdc++.h>
                  using namespace std;
                  int w[105], v[105];
                  int dp[1005];
                  int main()
                  {
                      int t,m;    
                      cin>>t>>m;
                      for(int i=1;i<=m;i++){
                         
                          cin>>w[i]>>v[i];
                      }
                      for(int i=1;i<=m;i++) 
                      {
                          for(int j=t;j>=w[i];j--){
                  		
                          
                             
                                  dp[j]=max(dp[j-w[i]]+v[i], dp[j]);
                              
                          }
                      }    
                      cout<<dp[t];
                      return 0;
                  }
                  
                  • @ 2023-3-24 18:19:26

                    浅浅格式化一下~

                    #include<bits/stdc++.h>
                    using namespace std;
                    int w[105],v[105];
                    int dp[1005];
                    int main(){
                        int t,m;    
                        cin>>t>>m;
                        for(int i=1;i<=m;i++){
                            cin>>w[i]>>v[i];
                        }
                        for(int i=1;i<=m;i++){
                            for(int j=t;j>=w[i];j--){
                                dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
                            }
                        }    
                        cout<<dp[t];
                        return 0;
                    }
                    
                • -2
                  @ 2021-10-31 9:53:55
                  • 1

                  信息

                  ID
                  678
                  时间
                  1000ms
                  内存
                  256MiB
                  难度
                  5
                  标签
                  递交数
                  435
                  已通过
                  158
                  上传者