Max Value Bags Carry Capacity

 

#include <stdio.h>

int max(int a, int b){

    return (a > b) ? a : b;

}

void kp(int W, int wt[], int val[], int n,int p[])

{

int i, w,h=0;

int K[n + 1][W + 1];

for (i = 0; i <= n; i++) {

for (w = 0; w <= W; w++) {

if (i == 0 || w == 0)

K[i][w] = 0;

else if (wt[i - 1] <= w)

K[i][w] = max(val[i - 1] +

K[i - 1][w - wt[i - 1]], K[i - 1][w]);

else

K[i][w] = K[i - 1][w];

}

}int res = K[n][W];

w = W;

for (i = n; i > 0 && res > 0; i--) {

if (res == K[i - 1][w])

continue;

else {

p[h++]=wt[i-1];

res = res - val[i - 1];

w = w - wt[i - 1];

}

}

}

int main(){

    int n,w;

    scanf("%d%d",&n,&w);

    int a[n],b[n],c[n];

    for(int i=0;i<n;i++){

        scanf("%d%d",&a[i],&b[i]);

        c[i]=0;

    }

    kp(w,a,b,n,c);

    for(int i=n-1;i>=0;i--){

        if(c[i]!=0)

        printf("%d ",c[i]);

    }

}