对一个二维数组c[i][j] i表示放入背包中物体的个数 j表示目前剩余空间量 c表示目前的最大价值 (w[],v[]分别表示每个物品的重量 价值)
基本的动态规划问题 用一个二维数组进行动态填表
动态规划的核心是将一个问题分解成若干个子问题 并对子问题进行当前状态的最优解的问题
对01背包问题每个子问题就是在已经满足此时价值最大的情况下 对是否加入下一个物品进行取决
c[i][j]=max(c[i-1][j],c[i-1][j-w[i]+v[i]);
01背包的二维填表问题实际就是一个递推问题 首先将第一行的（即c[0]）初始化 然后对j++ i++逐一的填表 得出结果
附上ac代码！！
#include<stdio.h>
int max(int x,int y)
{
if(x>y)
return x;
else
return y;
}
int main()
{
int n,i,j,sum[1010][1010],t,c,v[1020],x[1020];
scanf("%d",&t);
while(t--)
{
for(i=0;i<=1001;i++)
sum[0][i]=0;
scanf("%d %d",&n,&c);
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
}
for(i=1;i<=n;i++)
{
scanf("%d",&x[i]);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=c;j++)
{
if(j<x[i])
sum[i][j]=sum[i-1][j];
else
sum[i][j]=max(sum[i-1][j],sum[i-1][j-x[i]]+v[i]);
}
}
printf("%d\n",sum[n][c]);
}
return 0;
}
杭电oj 2602题
对于一维的还在理解当中。。。 吃饭吃饭！！