1 条题解

  • 3
    @ 2022-10-26 19:37:06

    背包问题

    这题,一个典型的背包问题。 也不能说典型吧......

    CODE:

    #include<bits/stdc++.h>
    
    using namespace std;
    int w[31],c[31],f[50001];
    int main(){
    	int m,n;
    	cin>>m>>n;
    	for(int i=1;i<=n;i++){
    		cin>>w[i]>>c[i];
    		c[i]*=w[i];
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=m;j>=w[i];j--){
    			if(j<w[i]){
    				f[j]=f[j-1];
    			} 
    			else{
    				f[j]=max(f[j],f[j-w[i]]+c[i]);
    			} 
    		}
    	}
    	cout<<f[m];
    	return 0;
    }
    

    哎哎,别走啊!!

    点个赞再走啊!!!

    信息

    ID
    531
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    10
    已通过
    6
    上传者