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

动静布局之01背包问题，c++实现

问题形容

01背包问题
问题剖析

1. 动静布局法分析：1.划分子问题，2.得出子问题的递推公式，3.填表

2. 划分子问题

   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)。

3. 递推公式

   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 示意用以后值和子问题的解联合，取最优
4. 填表
   

算法实现

#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;} 

后果如下