6 条题解

  • 3
    @ 2023-8-6 11:28:50
    #include<bits/stdc++.h>
    #define INF 0x3f3f3f3f
    using namespace std;
    int f[10005],v[110],w[110],num[110];
    int n,m;
    void OneZeroPack(int m,int v,int w) {
        for(int i=m;i>=v;i--)f[i]=max(f[i],f[i-v]+w);
    }
    void CompletePack(int m,int v,int w)  {
        for(int i=v;i<=m;i++)f[i]=max(f[i],f[i-v]+w);
    }
    void MultiplePack(int m,int v,int w,int num){
        if(v*num>=m){CompletePack(m,v,w);return ;}
        int k=1;
        for(k=1;k<=num;k<<=1){OneZeroPack(m,k*v,k*w);num=num-k;}
        if(num)OneZeroPack(m,num*v,num*w);
    }
    int main(){
        while(cin>>m>>n){
            for(int i=0;i<n;i++)cin>>v[i]>>w[i]>>num[i];
            memset(f,0,sizeof(f));
            for(int i=0;i<n;i++)MultiplePack(m,v[i],w[i],num[i]);
            cout<<f[m]<<endl;
        }
        return 0;
    }
    
    • 1
      @ 2025-5-18 20:12:52
      #include<bits/stdc++.h>
      using namespace std;
      const int N = 1000 + 10;
      int m , w[N] , c[N] , dp[1010] , n , s[N];
      int main(){
      	cin >> m >> n;
      	for(int i = 1;i <= n;i++)
      	    cin >> w[i] >> c[i] >> s[i];
      	for(int i = 1;i <= n;i++)
              for(int j = m;j >= w[i];j--) 
                  for(int k = 1;k <= s[i];k++)
                  {
                  	if(k * w[i] > j)
                  	    dp[j] = dp[j];
                  	else
                  	    dp[j] = max(dp[j] , dp[j - w[i] * k] + c[i] * k);
      			}
      	cout << dp[m];
      	return 0;
      }
      • 0
        @ 2023-11-11 10:18:05

        #include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int f[10005],v[110],w[110],num[110]; int n,m; void OneZeroPack(int m,int v,int w) { for(int i=m;i>=v;i--)f[i]=max(f[i],f[i-v]+w); } void CompletePack(int m,int v,int w) { for(int i=v;i<=m;i++)f[i]=max(f[i],f[i-v]+w); } void MultiplePack(int m,int v,int w,int num){ if(vnum>=m){CompletePack(m,v,w);return ;} int k=1; for(k=1;k<=num;k<<=1){OneZeroPack(m,kv,kw);num=num-k;} if(num)OneZeroPack(m,numv,num*w); } int main(){ while(cin>>m>>n){ for(int i=0;i<n;i++)cin>>v[i]>>w[i]>>num[i]; memset(f,0,sizeof(f)); for(int i=0;i<n;i++)MultiplePack(m,v[i],w[i],num[i]); cout<<f[m]<<endl; } return 0; }

        • 0
          @ 2023-8-6 11:30:03
          #include <iostream>
          #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 w[N],v[N],dp[N],n,m,len ,ww,vv,num;
          int main(){
          	cin >> m >> n;
          	for(int i=1; i<=n ;i++)
          	{
          		cin >> ww >> vv >> num;
          		int cnt = 1;
          		while(cnt <= num){
          			w[++len]=cnt*ww;
          			v[len]=cnt*vv;
          			num -= cnt;
          			cnt <<= 1;
          		}
          		if(num > 0){
          			w[++len]=num*ww;
          			v[len]=num*vv;
          		}
          		
          	}
          	n = len;
          	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;
          }//二进制解法
          
          • -3
            @ 2023-8-6 11:29:20

            #include

            #include

            #include

            #include

            #include<string.h>

            #include

            #include

            using namespace std;

            const int N=6e3+10;

            const int INF=0x3f3f3f3f;

            int m,n,w[N],v[N],dp[N],i,j,ww,vv,len,num1,cnt=1;

            int main(){

            cin>>m>>n;
            
            for(i=1;i<=n;i++){
            
            	cin>>ww>>vv>>num1;
            
            	cnt=1;
            
            	while(cnt<=num1){
            
            		w[++len]=cnt*ww;
            
            		v[len]=cnt*vv;
            
            		num1-=cnt;
            
            		cnt<<=1;
            
            	}
            
            	if(num1>0){
            
            		w[++len]=num1*ww;
            
            		v[len]=num1*vv;
            
            	}
            
            }
            
            n=len;
            
            for(i=1;i<=n;i++){
            
            	for(j=m;j>=w[i];j--){
            
            		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            
            	}
            
            }
            
            cout<<dp[m]<<endl;
            
            return 0;
            

            }

            • -3
              @ 2023-4-21 21:19:22
              #include <iostream>
              #include <cstdio>
              #include <algorithm>
              #include <string>
              #include <cstring>
              #include <cstdlib>
              #include <cmath>
              #include <stack>
              #include <queue>
              #include <set>
              #include <map>
              #include <vector>
              #include <ctime>
              #include <cctype>
              #include <bitset>
              #include <utility>
              #include <sstream>
              #include <complex>
              #include <iomanip>
              #define inf 0x3f3f3f3f
              typedef long long ll;
              using namespace std;
              int N,V,dp[210];
              struct node
              {
                  int n;//空间
                  int c;//价值
                  int w;//数量
              } p[210];
              int main()
              {
                  scanf("%d%d",&V,&N);
                  for(int i=1; i<=N; i++)
                      scanf("%d%d%d",&p[i].n,&p[i].c,&p[i].w);
                  for(int i=1; i<=N; i++)
                  {
                      if(p[i].w*p[i].n>=V)
                      {
                          for(int j=p[i].n; j<=V; j++)
                              dp[j]=max(dp[j],dp[j-p[i].n]+p[i].c);
                      }
                          for(int k=1; k<p[i].w; p[i].w-=k,k=k*2)
                              for(int j=V; j>=k*p[i].n; j--)
                                  dp[j]=max(dp[j],dp[j-k*p[i].n]+p[i].c*k);
                          for(int j=V; j>=p[i].n*p[i].w; j--)
                              dp[j]=max(dp[j],dp[j-p[i].w*p[i].n]+p[i].c*p[i].w);
                  }
                  printf("%d\n",dp[V]);
                  return 0;
              }
              
              • 1

              信息

              ID
              1734
              时间
              1000ms
              内存
              256MiB
              难度
              5
              标签
              递交数
              186
              已通过
              73
              上传者