题解 | #【模板】01背包#

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

int main() {
    int volume;
  
    int quantity;
    scanf("%d %d",&quantity,&volume);
// 01背包
 int *a = (int*)malloc(sizeof(int)*(quantity+1));
  int *b = (int*)malloc(sizeof(int)*(quantity+1));
 a[0] = 0;
 b[0] = 0;
 for(int i = 1;i<=quantity;i++){
    scanf("\n%d",&a[i]);
     scanf("\n%d",&b[i]);
 }



 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 = 1;j<=volume;j++){
        if(j>=a[i]){
            dp[i][j] = dp[i-1][j]>dp[i-1][j-a[i]]+b[i]?dp[i-1][j]:dp[i-1][j-a[i]]+b[i];
            // printf("  dp[%d][%d] is %d",i,j,dp[i][j]);
        }
        else {
            dp[i][j] = dp[i-1][j];
        }

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

 int **dp1 = (int**)malloc(sizeof(int*)*(quantity+1));
 for(int i = 0;i<quantity+1;i++){
    dp1[i] = (int*)malloc(sizeof(int)*(volume+1));
 }
  // 完全装满的只能通过完全装满的来转移
  // 例如 10 容量，2 10；3 30；5 10；dp[i][10]只能由dp[i][2],dp[i][3],dp[i][5]，dp[i][0] = 0变化得到
 //所以给其他不符合的都设置标志位，符合的才能继续运算
for(int i = 0;i<quantity+1;i++){
    for(int j = 0;j<volume+1;j++){
        dp1[i][j] = -10000;
        if(j==0){
             dp1[i][j] = 0;
        }
    }
}


for(int i = 1;i<quantity+1;i++){
    for(int j = 1;j<=volume;j++){
        if(j>=a[i]){
             dp1[i][j] = dp1[i-1][j]>dp1[i-1][j-a[i]]+b[i]?dp1[i-1][j]:dp1[i-1][j-a[i]]+b[i];
  
        }
        else {
            dp1[i][j] = dp1[i-1][j];
           
        }
    

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

printf("%d\n",dp[quantity][volume]);
if(dp1[quantity][volume]>0){
printf("%d",dp1[quantity][volume]);
}else{printf("0");}
// for(int i =quantity;i>=quantity;i--){
// if(dp1[i][volume]==volume){
//     printf("%d",dp2[i][volume]);
//     return 0;
// }
// }

// for(int i = 1;i<quantity+1;i++){
//     for(int j = 1;j<=volume;j++){
//      printf("%d ",dp1[i][j]);


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

    return 0;
}