01背包

题目：

有N种物品（每种物品只有一件）和一个容量为V的背包。放入第i件物品耗费的费用为Ci,得到的价值是vi,求解将哪些物品装入背包可使得价值总和最大。
状态转移方程：
f[i][j]=max(f[i-1][j - w[i-1]] + v[i-1], f[i-1][j]);

物品信息 状态转移表格（灰色为初始化）

代码一：

#include<malloc.h>
#include<string.h>
int max(int a,int b){          //定义取两个数之间最大数的函数
    return a>b?a:b;
}
int main(){
    int n,i,j,V;
    scanf("%d %d",&n,&V);      //n表示有的商品种类，V表示背包大小
    int *w=(int*)malloc(n*sizeof(int));
    int *v=(int*)malloc(n*sizeof(int));
    for(i=0;i<n;i++){                //输入n个商品的重量/大小
        scanf("%d",&w[i]);
    }
    for(j=0;j<n;j++){
        scanf("%d",&v[j]);    //输入n个商品的价值
    }
    int **f=(int**)malloc((n+1)*sizeof(int*));  //定义一个二维数组保存状态
    for(i=0;i<=n;i++){
        f[i]=(int*)malloc((V+1)*sizeof(int));
    }
    for(i=0;i<=n;i++){
        f[i][0]=0;
    }
    for(i=0;i<=V;i++){
        f[0][i]=0;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=V;j++){
            if(j>=w[i-1]){
                f[i][j]=max(f[i-1][j - w[i-1]] + v[i-1], f[i-1][j]);  //状态转移方程
            }else{
                 f[i][j] = f[i-1][j];
            }
        }
    }
    for(i=0;i<=n;i++){
        for(j=0;j<=V;j++){
            printf("%d ",f[i][j]);
        }
        printf("\n");
    }
    printf("\n%d\n",f[n][V]);
}

样例输出

输出演示