动态规划——背包问题

问题描述

一个旅行者有一个最多能装10公斤的背包，现在有5中物品，每件的重量分别是2、2、6、5、4公斤，每件物品的价值分别为6、3、5、4、6， 需要将物品放入背包中，要怎么样放才能保证背包中物品的总价值最大？

算法分析 

一个旅行者有一个最多能装m公斤的背包，现在有n种物品，每件的重量分别是W1、W2、……、Wn，每件物品的价值分别为C1、C2、……、Cn， 需要将物品放入背包中，要怎么样放才能保证背包中物品的总价值最大？

如果要到达V(i,j)这一个状态有几种方式？

第一种是第i件商品没有装进去，第二种是第i件商品装进去了。

没有装进去,就是V(i-1,j);如果装进去第i件商品，是V(i-1,j-w(i))

由于最优性原理,V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优。

输入样例 

背包的最大容量:10

物品的数量:5

物品的重量:2  2  6  5  4

物品的价值:6  3  5  4  6

输出样例

  物品信息菜单栏
********************
编号    重量    价值
  1         2         6
  2         2         3
  3         6         5
  4         5         4
  5         4         6

记录物品装入后的背包状态：
1    2    3    4    5    6    7     8     9    10

0    6    6    6    6    6    6     6     6     6
0    6    6    9    9    9    9     9     9     9
0    6    6    9    9    9    9    11   11   14
0    6    6    9    9    9   10   11   13   14
0    6    6    9    9   12  12   15   15   15
选中的物品是:1  2  5
最大物品价值为: 15

程序运行截图

 程序代码

#include <iostream>
#include<iomanip>//用于引入setw，设置输出格式
using namespace std;
int V[100][100];//前i个物品装入容量为j的背包中获得的最大价值
/*返回两数中的较大者*/
int max(int a, int b) {
    if (a >= b)
        return a;
    else
        return b;
}
int KnapSack(int n, int weight[], int value[], int C) {
    /*填表，其中第一行和第一列全为0，即V(i,0)=V(0,j)=0；*/
    for (int i = 0; i <= n; i++)
        V[i][0] = 0;
    for (int j = 0; j <= C; j++)
        V[0][j] = 0;
    /*输出物品重量单价等信息*/
    cout << endl << "   " << "物品信息菜单栏" << endl << "********************" << endl;
    cout << "编号\t重量\t价值\t" << endl; //菜单栏 1
    for (int m = 1; m <= n; m++) //m为物品编号
    {
        cout << " " << m << "\t " << weight[m - 1] << "\t " << value[m - 1] << endl;
    }
    /*输出背包装入物品后的状态*/
    cout << endl << "记录物品装入后的背包状态：" << endl;
    for (int k = 1; k <= C; k++)
    {
        cout << std::left << setw(5) << k;//使用setw()函数设置输出宽度为5
    }
    cout << endl << endl;
    /*动态规划算法，求最大价值*/
    for (int i = 1; i <= n; i++) {// 遍历每个物品
        for (int j = 1; j <= C; j++) {// 遍历每个容量
            if (j < weight[i - 1]) { //包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的
                V[i][j] = V[i - 1][j];
                cout << std::left << setw(5) << V[i][j];
            }
            else { //还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个
                V[i][j] = max(V[i - 1][j], V[i - 1][j - weight[i - 1]] + value[i - 1]);
                cout << std::left << setw(5) << V[i][j];
            }
        }
        cout << endl;
    }
    return V[n][C];
}
/*回溯判断哪些物品被选中装入背包*/
void Judge(int C, int n, int weight[])
{
    int j = C;
    int* state = new int[n];
    for (int i = n; i >= 1; i--) {
        if (V[i][j] > V[i - 1][j]) {
            state[i] = 1;
            j = j - weight[i - 1];
        }//如果装了就标记，然后减去相应容量
        else {
            state[i] = 0;
        }
    }
    cout << "选中的物品是:";
    for (int b = 1; b <= n; b++) {
        if (state[b] == 1) {
            cout << b << " ";
        }
    }
    cout << endl;
}
int main() {
    int n;              //物品数量
    int Capacity;       //背包最大容量
    cout << "请输入背包的最大容量:";
    cin >> Capacity;
    cout << "输入物品数:";
    cin >> n;
    int* weight = new int[n]; //物品的重量
    int* value = new int[n];  //物品的价值
    cout << "请分别输入物品的重量:";
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
    }
    cout << "请分别输入物品的价值:";
    for (int c = 0; c < n; c++) {
        cin >> value[c];
    }
    int s = KnapSack(n, weight, value, Capacity); //获得的最大价值
    Judge(Capacity, n, weight);                   //调用函数判断那些物品被选择
    cout << "最大物品价值为: " << s << endl;
    delete[] weight;
    delete[] value;//释放动态数组空间
    return 0;
}