Question

求大神给一份C语言01背包的代码，要每一行都有注释，谢谢！

没有注释看不懂，如果还能能有一点点讲解就最好了，谢谢！
#include <stdio.h>
#include <string.h>

int f[1010],w[1010],v[1010];

int max(int x,int y)
{
if(x>y) return x;
else return y;
}

int main()
{
int t,m,i,j;
memset(f,0,sizeof(f));
scanf("%d %d",&t,&m);
for (i=1;i<=m;i++)
scanf("%d %d",&w[i],&v[i]);
for (i=1;i<=m;i++)
{
for (j=t;j>=w[i];j--)
{
if(w[i]<=t)
f[j]=max(f[j-w[i]]+v[i],f[j]);
}
}
printf("%d",f[t]);
printf("\n");

getch();
return 0;
}

还有没有更简单的方法？求程序和注释！

Answer 1

这是一个背包问题，该算法已经是最简单的了，还有递归算法，我觉得更麻烦。对你的代码进行解释如下：

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

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

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

int main(){
    int t,m,i,j;
    memset(f,0,sizeof(f));  //总价值初始化为0
    scanf("%d %d",&t,&m);  //输入背包承重量t、物品的数目m
    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--){
            f[j]=max(f[j-w[i]]+v[i],f[j]);
            //在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
        }
    }
    printf("%d",f[t]);  //输出承重量为t的背包的总价值
    printf("\n");
    getch();
    return 0;
}

Answer 2

什么意思。。说清楚一点啊。

追问

要一份01背包的代码（C语言），
要尽量每一行都有注释，明白了吗？