01背包问题--C语言代码

01背包问题的解释可以看百度百科：01背包问题

自己不太懂，不过看这个代码好像有点理解的意思了，就先收藏一下代码吧

/********************************************************/
/*背包问题：有m件物品和一个承重为t的背包。              */
/*          第i件物品的重量是w[i]，价值是v[i]。         */
/*          求解将哪些物品装入背包可使这些物品的        */
/*          重量总和不超过背包承重量t，且价值总和最大。 */
/********************************************************/

#include <stdio.h>
#include <string.h>

int f[1010]; // 记录不同承重量背包的总价值
int w[1010]; // 记录不同物品的重量
int v[1010]; // 记录不同物品的价值

//返回x,y的最大值
int max(int x,int y)
{
    if(x>y)
        return x;
    return y;
}

int main()
{
    int t; // 背包的承重量
    int m; // 物品的数量
    int i,j; // 临时变量

    memset(f,0,sizeof(f));  //总价值初始化为0
    printf("请输入背包承重量 物品的数量：\n");
    scanf("%d %d",&t,&m);  //输入背包承重量t、物品的数目m
    printf("请输入每件物品的重量 价值：\n");
    for(i = 1; i <= m; i++)
        scanf("%d %d",&w[i],&v[i]);  //输入m组物品的重量w[i]和价值v[i]

    //尝试放置每一个物品
    for(i = 1; i <= m; i++)
    {  
        for(j = t; j >= w[i]; j--)
        {
            //在放入第i个物品前后，检验不同j承重量背包的总价值
            //如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
            f[j] = max(f[j-w[i]]+v[i],f[j]);
        }
    }


    printf("装入背包的物品\"重量:价值\" ：\n");
    j=t;  // 临时记录背包重量
    for(i=1;i<=m;i++)
    {
        // 如果物品被放入，一定符合这样的条件
        if(f[j] == f[j-w[i]] + v[i])
        {
            printf("%d:%d\n",w[i],v[i]);
            j -= w[i];
        }
    }


    printf("背包最终重量 价值\n");
    printf("%d %d\n",t,f[t]);  
    getch();
    return 0;
}