【文件属性】:
文件名称:动态规划解决0-1背包
文件大小:2KB
文件格式:CPP
更新时间:2011-11-19 07:18:26
动态规划 背包
void knapsack(int val[],int wei[],int c,int n,int**m) //求最优值
{
int jmax=min(wei[n]-1,c);
for(int j=0;j<=jmax;j++)
m[n][j]=0;
for(int jj=wei[n];jj<=c;jj++)
m[n][jj]=val[n];
for(int i=n-1;i>1;i--){ //递归部分
jmax=min(wei[i]-1,c);
for(int j=0;j<=jmax;j++)
m[i][j]=m[i+1][j];
for(int jj=wei[i];jj<=c;jj++)
m[i][jj]=max(m[i+1][jj],m[i+1][jj-wei[i]]+val[i]);
}