0/1背包有关问题的代码分析

0/1背包问题的代码分析
今天照着书上写了一下0／1背包问题的代码，发现书上写的不对，出现了几处错误，但不知怎么改正，请各位指教。
代码如下：
#include<iostream>
#include<stdio.h>
using namespace std;
int knapsack_dynamic(int w[],int p[],int n,int m,bool x[]);
int main()
{
int n,m,v,i;
//n stands for the total count of all the objects,
//m stands for the loading capacity of the knapsack
//v stands for the maximum value of the objects loaded into the knapsack
while((scanf("%d%d",&n,&m))!=-1 && n>0 && m>0)
{
int *w=new int[n+1];
//w[n] stores the weights of the n objects
int *p=new int[n+1];
//p[n] stores the values of the n objects
bool *x=new bool[n+1];
//if x[i] is true,then the i'th object is to be loaded into the knapsack
w[0]=p[0]=x[0]=0;
for(i=1;i<=n;++i)
scanf("%d%d",w+i,p+i);
printf("The maximum value is:%d\n",knapsack_dynamic(w,p,n,m,x));
for(i=0;i<n;++i)
printf("%d ",x[i]?1:0);
printf("\n");
delete []w;
delete []p;
delete []x;
}
}
int knapsack_dynamic(int w[],int p[],int n,int m,bool x[])
{
int i,j,k;
int v,*opt[m+1]=new int[n+1][m+1];
for(i=0;i<=n;++i)
{ opt[i][0]=0; x[i]=false;}
for(i=0;i<=m;++i)
opt[0][i]=0;
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
opt[i][j]=opt[i-1][j];
if(w[i]<=j && opt[i-1][j-w[i]]+p[i]>opt[i-1][j])
opt[i][j]=opt[i-1][j-w[i]]+p[i];
}
}
j=m;
//calculate the objects loaded into the knapsack with recursive algorithm
for(i=n;i>0;--i)
if(opt[i][j]>opt[i-1][j])
{ x[i]=true; j-=w[i];}
v=opt[n][m];
delete []opt;
return v;
}
系统提示如下：

01knapsack.c++: 在函数‘int knapsack_dynamic(int*, int*, int, int, bool*)’中:
01knapsack.c++:34:31: 错误： ‘m’不能出现在常量表达式中
01knapsack.c++:34:34: 错误：可变大小的对象‘opt’不能被初始化
01knapsack.c++:54:11: 警告：删除数组‘int* opt [(((unsigned int)((int)m)) + 1)]’ [默认启用]
还有一个问题，就是int *opt[m+1]=new int[n+1][m+1]之后如何删除opt所指向的内存空间？
是我写的那样吗？

------解决方案--------------------
m’不能出现在常量表达式中：无法动态申请二维数组，第二维必须指定常量。
可以申请一维数组，然后当做二维使用，new int[(n+1) * (m+1)];，不过使用方式和二维数组不一样。
用这种方式使用num[i * n + j]，i表示第一维，j表示第二维，n是第一维的长度。
下边是我写的01背包

C/C++ code


/*
**功能     ：O(NV)空间复杂度的01背包算法，该算法可以保存路径，状态方程式f(i,v) = max(f(i-1,v),f(i-1,v-c[i])+w[i])
**参数     ：
           ：items    ：给定的要放入背包的物品
           ：capacity ：给定的背包的容量
           ：bag      ：放入背包的物品
**返回     ：最大价值
*/
int KnapSack01(const vector<BagItem> &items, int capacity, vector<BagItem> &bag)
{
    //ASSERT(bag != NULL);
    vector<BagItem>::size_type item_size = items.size();
    int value_size = static_cast<int>(item_size) + 1;
    int value_cap = capacity + 1;
    int * max_values = new int[value_size * value_cap](); //如果要求恰好装满，则除了第0个元素外都应该初始化为负无穷
    
        //全部初始化为0，省去初始化0个物品放入重i的背包里以及i个物品放入重0的背包里
    
    for(int i = 1; i < value_size; i++)
    {
        for(int j = 1; j < value_cap; j++)
        {
            if(items[i - 1].GetWeight() > j)
            {
                max_values[i * value_cap + j] = max_values[(i - 1) * value_cap + j];
            }else
            {
                max_values[i * value_cap + j] = max(max_values[(i - 1) * value_cap + j],\
                    max_values[(i - 1) * value_cap + j - items[i - 1].GetWeight()] + items[i - 1].GetValue());
            }
        }
    }

    int tmp_capacity = capacity;
    int total_val = 0;
    for(int i = value_size - 2; i > 0; i--)
    {
        if(max_values[i * value_cap + tmp_capacity] > max_values[(i - 1) * value_cap + tmp_capacity])
        {
            total_val += items[i - 1].GetValue();
            bag.push_back(items[i - 1]);
            tmp_capacity -= items[i - 1].GetWeight();
        }
    }
    delete max_values;
    return total_val;
}

/*
**功能     ：O(V)空间复杂度的01背包算法，该算法不保存路径，状态方程f(v) = max(f(v), f(v-c[i])+w[i])
**参数     ：
           ：items    ：给定的要放入背包的物品
           ：item_num ：物品数目
           ：capacity ：给定的背包的容量
**返回     ：最大价值
*/
int KnapSack01(const vector<BagItem> &items, int capacity)
{
    vector<BagItem>::size_type item_size = items.size();
    int value_size = static_cast<int>(item_size) + 1;
    int * max_values = new int[capacity + 1](); //如果要求恰好装满，则除了第0个元素外都应该初始化为负无穷
    
    int tmp_value;
    for(int i = 1; i < value_size; i++)
    {
        for(int j = capacity; j > items[i - 1].GetWeight(); j--)
        {
            tmp_value = max_values[j - items[i - 1].GetWeight()] + items[i - 1].GetValue();
            if(max_values[j] < tmp_value)
            {
                max_values[j] = tmp_value;
            }
        }
    }

    int total_val = max_values[capacity];
    delete max_values;
    return total_val;
}

0/1背包有关问题的代码分析

相关推荐