1 条题解

  • 0
    @ 2023-6-11 12:20:58

    C :

    #include <stdio.h>
    int V;
    int n;
    int a[31];  
    int dp[20001]={0};  
    
    int main ()
    {
        int i,j;
        int t;
    	scanf("%d",&V);
    	scanf("%d",&n);
        
    	for(i=0;i<n;i++)
    		scanf("%d",&a[i]);
    	
    	for(i=0;i<n;i++)
    	{
    		for(j=V;j>=a[i];j--)
    		{
    			if(dp[j]>( dp[j-a[i]]+a[i] ))
    			   dp[j]=dp[j];
    			else
    				dp[j]=dp[j-a[i]]+a[i]; 
    			
    		}
    	}	
        printf("%d",V-dp[V]); 
        return 0;
    }
    

    C++ :

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

    信息

    ID
    2651
    时间
    1000ms
    内存
    16MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者