背包算法最优解的问题

Question

若果把背包问题 直接按价值降序排列 和 按单位质量价值降序排列 两者的结果进行比较,能不能得出最优解?如果不能,在不涉及递归和穷举的前提下,有什么方法可以得出最优解?

Answer 1

选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断.

使用动态规划来处理背包问题:
背包的状态转换方程 f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }
f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。
Pi表示第i件物品的价值。

参考代码:

 #include <iostream>
#include <vector> 
using namespace std;
//物品类 
class packitem{
    public:
        packitem(int w, int v):weight(w), value(v){}
        int weight;
        int value;
};
int matrix[5][10] = {0};
int maxValue(int matrix[][10], vector<packitem*> vecpack, int bagsize, int bagweight){
    for(int i = bagsize - 1; i >= 0; --i){
        for(int j = 0; j < bagweight; ++j){
            packitem item = *vecpack[i];
            if(item.weight > j + 1){
                //当前背包不能装下此物品
                if(0 == j){
                    matrix[i][j] = 0;
                }
                else{
                    matrix[i][j] = matrix[i + 1][j];
                }
            }
            else{
                int valueInbag = 0;
                if( i == bagsize - 1|| j - item.weight + 1 < 0){
                    matrix[i][j] = item.value;
                    continue;
                }
                else{
                    int tmp = 0;
                    if (j - item.weight >= 0)
                        tmp = j - item.weight;
                    valueInbag = matrix[i + 1][tmp] + item.value;
                    matrix[i][j] = max(matrix[i + 1][j], valueInbag);
                }
            }
        }
    }

    for(int i = 0; i < bagsize; ++i){
        for(int j = 0; j < bagweight; ++j){
            cout<<matrix[i][j]<<" "; 
        }
        cout<<endl;
    }
    return matrix[0][bagweight - 1];

}
int main()
{
    vector<packitem*> tmp; 
    int w[] = {2,2,6,5,4};
    int v[] = {6,3,5,4,6};
    int bagweight = 10;
    for(int i = 0; i < 5; ++i){
        tmp.push_back(new packitem(w[i], v[i]));
    }
    int result = maxValue(matrix, tmp, 5, bagweight);

    for(int i = 0; i < 5; ++i){
        delete tmp[i];
    }
    tmp.clear();

    cout<<result<<endl;
    return 0;
}