01背包问题动态规划

#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
    printf("输入背包承重量t、物品的数目m\n");
    scanf("%d %d",&t,&m);  //输入背包承重量t、物品的数目m
    for(i=1;i<=m;i++)
    {
        printf("%d:",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;
}