Marks_Liszt
2016-05-19 03:59
采纳率: 100%
浏览 1.6k
已采纳

背包算法最优解的问题

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

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • lbcab 2016-05-19 04:42
    已采纳

    选取价值最大者。反例:
    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;
    }
    
    打赏 评论
  • ZSGG_ACM 2016-05-19 04:56

    百度背包九讲,你会找到你要的答案

    打赏 评论
  • havedream_one 2016-05-19 05:27
    打赏 评论

相关推荐 更多相似问题