题解 | #[NOIP2001]装箱问题#

//01装箱 ，至于为什么用二维矩阵，我也不知道为什么

#include <stdarg.h>
#include <stdio.h>
#include<malloc.h>

 void minClose(int *arr,int count, int quantity,int volume,int sum ,int min){
    if(count>=quantity)return ;
    if(count<quantity){
        // 不加
               printf("\n%d",min);

        minClose(arr,count+1,quantity,volume,sum,min);


// 加
       sum = sum+arr[count];
       if(sum<=volume){
        min = min<volume-sum? min:volume-sum;
       printf("\n%d",min);
       }
       minClose(arr, count+1,quantity,volume,sum,min);
    }
 }
int main() {
    int volume;
    scanf("%d",&volume);
    int quantity;
    scanf("%d",&quantity);
// 01背包
 int *a = (int*)malloc(sizeof(int)*(quantity+1));
 a[0] = 0;
 for(int i = 1;i<=quantity;i++){
    scanf("\n%d",&a[i]);
 }


// 暴力穷举
// int min = 100000;
//   minClose(a, 0, quantity, volume, 0,min);
 int **dp = (int**)malloc(sizeof(int*)*(quantity+1));
 for(int i = 0;i<quantity+1;i++){
    dp[i] = (int*)malloc(sizeof(int)*(volume+1));
 }
for(int i = 0;i<quantity+1;i++){
    for(int j = 0;j<volume+1;j++){
        dp[i][j] = 0;
    }
}

for(int i = 1;i<quantity+1;i++){
    for(int j = volume;j>=0;j--){
        if(j>=a[i]){
            dp[i][j] = dp[i-1][j]>dp[i-1][j-a[i]]+a[i]?dp[i-1][j]:dp[i-1][j-a[i]]+a[i];
            // printf("  dp[%d][%d] is %d",i,j,dp[i][j]);
        }
        else {
            dp[i][j] = dp[i-1][j];
        }

    }
    // printf("\n");
}

printf("%d",volume-dp[quantity][volume]);
    return 0;
}