关于c++:动态规划之01背包问题c实现

6次阅读

共计 1455 个字符，预计需要花费 4 分钟才能阅读完成。

01 背包问题
问题剖析

动静布局法分析：1. 划分子问题，2. 得出子问题的递推公式，3. 填表
划分子问题
1. 用数组 Vn 存储价值和分量关系，行示意物体，列示意分量
2. 第 0 行和第 0 列设置为 0，没有物体的时候价值没 0，分量为 0 的时候物体无论多少价值也为 0
3. 如果第 i 个物体分量小于以后总重量 j，则取前 i - 1 和第 i 个物体组合的最优值，否则该物体不能够放进背包，取前 i - 1 个物体的最优价值(例如装入以后物体，则残余分量用来装后面残余物体的最优装法失去以后最优价值，得出 max{V(i-1, j), V(i-1, j-wi)+vi }；不装入以后物体，则以目前分量装后面所有物体的最优法），得出 V(i-1, j)。
递推公式
1. 不装入背包时：V(i-1, j) j < wi
2. 装入背包时：max{V(i-1, j), V(i-1, j-wi)+vi } j >= wi
3. V(i-1, j-wi)+vi 示意用以后值和子问题的解联合，取最优
填表

#include<iostream>
using namespace std;
struct Node {
    int value;
    int weight;
}; 

// 物体，长度 
void packageHander(Node arr[], int n, int c) {int V[n][c+1], i;
    // 第 0 行和第 0 列设置为 0，没有物体的时候价值没 0，分量 3 为 0 的时候物体无论多少价值也为 0
    for (i = 0; i < n; i++) {V[i][0] = 0;
    } 
    for (i = 0; i <= c; i++) {V[0][i] = 0;
    } 
    for (i = 1; i < n; i++) {
        // 分量从 1 到 c 
        for (int j = 1; j <= c; j++) {
            // 分量小于目前总量 
            // 如果第 i 个物体分量小于以后总重量 j，则取前 i - 1 和第 i 个物体组合的最优值，否则该物体不能够放进背包，取前 i - 1 个物体的最优价值 
            if (arr[i-1].weight <= j) {V[i][j] = max(V[i-1][j], V[i-1][j-arr[i-1].weight]+arr[i-1].value);
            } else {V[i][j] = V[i-1][j];
            }
        } 
    }
    for (i = 0; i <= c; i++) {cout<<i<<"\t";}
    cout<<endl;
    for (i = 0; i < n; i++) {for (int j = 0; j <= c; j++) {cout<<V[i][j]<<"\t";
        }
        cout<<endl;
    }
    int j = 0;
    // 如果以后值比前一个值大，阐明被取了，就取以后值，而后减去分量，分量作为列 
    for (i=n, j=c; i>0; i--) {if (V[i][j] > V[i-1][j]) {x[i-1] = 1;
            j = j - arr[i-1].weight;
        } else {x[i-1] = 0;
        } 
    }
    cout<<"选取计划为"; 
    for (i = 0; i<n-1; i++) {cout<<x[i]<<" ";
    }
    cout<<endl;
}


int main() {
    int n = 6;
    Node a[n];
    a[0].value = 6;
    a[0].weight = 2;
    a[1].value = 3;
    a[1].weight = 2;
    a[2].value = 5;
    a[2].weight = 6;
    a[3].value = 4;
    a[3].weight = 5;
    a[4].value = 6;
    a[4].weight = 4;
    for (int i = 0; i < n-1; i++) {cout<<"val"<<a[i].value<<"weight"<<a[i].weight<<endl;
    }
    packageHander(a, n, 10);
    return 0;
}

正文完