0-1背包2

/*逆推*/

#include <stdio.h>
#include <string.h>
#define N 100
int d[N][N];  //存储选取物体的过程
int capacity; //包的容量
int v[N];     //每个物体的体积
int w[N];     //每个物体的权值
int n;        //物体的数量

void Init()
{
    int temp, i;
    memset(v, 0, sizeof(v));
    memset(w, 0, sizeof(w));
    printf("Please input the number of n :");
    scanf("%d", &n);
    printf("Please input the capacity of backage:");
    scanf("%d", &capacity);
    printf("Please input each volume of the object:");
    for(i=1; i<=n; i++)
    {
        scanf("%d", &temp);
        v[i] = temp;
    }
    printf("Please input each weight of object:");
    for(i=1; i<=n; i++)
    {
        scanf("%d", &temp);
        w[i] = temp;
    }
}

void backage()
{
    memset(d, 0, sizeof(d));
    for(int i=n; i>=1; i--)
        for(int j=0; j<=capacity; j++)
        {
            d[i][j] = (i==n ? 0:d[i+1][j]);
            if(j >= v[i])
            {
                if(d[i][j] >= d[i+1][j-v[i]]+w[i])   ;
                else  d[i][j] = d[i+1][j-v[i]]+w[i];
            }
        }
}

void print()
{
    for(int i=0; i<=n+1; i++)
    {
        for(int j=0; j<=capacity; j++)
            printf("%3d", d[i][j]);
        printf("\n");
    }
    printf("The max value of backage is:%d\n", d[1][capacity]);
    getchar();
}

void main()
{
    Init();
    backage();
    print();
}