C 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2022-04-06

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<math.h>

int cmp(const void* a, const void* b){
    return *(int*)a-*(int*)b;
}

int max(int a,int b){
    return a>b ? a : b;
}
//一维dp数组
int main(){
    int V,n;
    scanf("%d",&V);
    scanf("%d",&n);
    int* v = (int*)calloc(n+1,sizeof(int));
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    
    qsort(v,n+1,sizeof(int),cmp);
    
    int* dp = (int*)calloc(V+1,sizeof(int));
    
    for(int i=1;i<=n;i++){
        for(int j=V;j>=v[i];j--){
            dp[j] = max(dp[j],v[i]+dp[j-v[i]]);
        }
    }
    
    printf("%d",V-dp[V]);    
        
    free(v);
    free(dp);
    return 0;
}

/* //二维
int main(){
    int V,n;
    scanf("%d",&V);
    scanf("%d",&n);
    int* v = (int*)calloc(n+1,sizeof(int));
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    
    qsort(v,n+1,sizeof(int),cmp);
    
    int** dp = (int**)calloc(n+1,sizeof(int*));
    for(int i=0;i<n+1;i++){
        dp[i] = (int*)calloc(V+1,sizeof(int));
        dp[i][0] = 0;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=V;j++){
            if(j>=v[i])dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-v[i]]);
            else dp[i][j] = dp[i-1][j];
        }
    }
    
    printf("%d",V-dp[n][V]);    
        
    free(v);
    free(dp);
    return 0;
}
*/

C 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-03-23

#include <stdio.h>

int a[40];
int f[20020]; //数组滚动
int n, v;
 
int main(){
    scanf("%d%d",&v,&n);
    for(int i = 1;i <= n;++ i) scanf("%d",&a[i]);
    f[0] = 1; //初始化
     
    for(int i = 1;i <= n;++ i){
        for(int j = v;j >= a[i];j --){ //j从0开始遍历到v,然后选与不选都设置为真
                f[j] = f[j] || f[j - a[i]];
        }
    }
    int ans = 0;
    for(int i = v;i >= 0;i --){ //倒序遍历
        if(f[i]){ //只要有为真的就说明此时是体积剩余最小的
            ans = v - i;
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-07-09

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

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-05-22

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int capacity = 0;
    int n = 0;
    cin >> capacity >> n;
    vector<int> V(n, 0);
    for(int i = 0; i < n; ++i)
    {
        cin>>V[i];
    }
    
    //start
    vector<int> maxV(capacity+1,0);
    for(int i = 0; i < n; ++i)
    {
        for(int j = capacity; j >= V[i]; j--)
        {
            if(V[i] <= capacity)
            {
                maxV[j] = max(maxV[j], maxV[j - V[i]]+V[i]);
            }
        }
    }
    cout<<capacity - maxV[capacity]<<endl;

    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-05-11

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int v;
    cin >> v;
    cin >> n;//dp[v]的意思为：容量为v时，能装的最大体积。
    vector<int>dp(v+1,0);//本质还是01背包问题，剩余空间最小就是价值最大的意思。01背包算出能装最多的空间，
    vector<int>volum(n);//再用v-dp[v]就得剩下的最小空间。
    for(int i = 0;i < n;i++)
        cin >> volum[i];
    for(int i = 0;i < n ;i++)
    {
        for(int j = v;j >= volum[i];j--)
        {
            dp[j] = max(dp[j],dp[j-volum[i]] + volum[i]);
        }
    }
    cout << v-dp[v] <<endl;
    return 0;
}