题解 | #【模板】完全背包#

#include <stdarg.h>
#include <stdio.h>
#include<malloc.h>
//完全背包和01背包的唯一区别就是两层循环中再添加一层，
/*
2 6
5 10
3 1
理解成：

2 6
5 10
5 10
3 1
3 1
即可
*/
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;
        }
    }


    int** dp1 = (int**)malloc(sizeof(int*) * (quantity + 1));
    for (int i = 0; i < quantity + 1; i++) {
        dp1[i] = (int*)malloc(sizeof(int) * (volume + 1));
    }
    for (int i = 0; i < quantity + 1; i++) {
        for (int j = 0; j < volume + 1; j++) {
            dp1[i][j] = -100900;
            if (j == 0) {
                dp1[i][j] = 0;
            }
        }
    }

    for (int i = 1; i < quantity + 1; i++) {
        for (int j = 1; j <= volume; j++) {

            int max  = dp[i - 1][j];
            int max1 = dp1[i - 1][j];
            for (int k = 1; k * a[i] <= j; k++) {
                max = max > dp[i - 1][j - k * a[i]] + k * b[i] ? max : dp[i -
                        1][j - k * a[i]] + k * b[i];
                max1 = max1 > dp1[i - 1][j - k * a[i]] + k * b[i] ? max1 : dp1[i -
                        1][j - k * a[i]] + k * b[i];

            }
            dp[i][j] = max;
            dp1[i][j] = max1;

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



//     for (int i = 1; i < quantity + 1; i++) {
//         for (int j = 1; j <= volume; j++) {
//    int max  = dp1[i - 1][j];
//         for(int k = 1;k*a[i]<=j;k++){
//             max =max > dp1[i - 1][j - k*a[i]] + k*b[i] ? max: dp1[i -
//                            1][j -k*a[i]] + k*b[i];

//         }
//            dp1[i][j] = max;


//         }
//         // 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 ",dp[i][j]);


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

    return 0;
}