题目：
有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]);
}
样例输出
输出演示
