问题描述

已知n种物品的体积、价值和数量,背包的容积为C,从物品中选择装入背包的物品,每种物品装入数量不超过物品的数量,请设计算法求出装入价值最大的装法。

要求:

(1) 输入n种物品的体积、价值和数量,输入背包的容积。

(2) 分析给出带限制的整数背包问题的递归公式。

(3) 利用动态规划算法编程求解,输出每种物品装入背包的个数和装入背包的最大价值。

算法分析

问题分析:

这是一个有限制物品数量的背包,一个典型的动态规划问题。在这里,我们不仅要使用二维数组解出背包最大价值,还要直到放了哪个物品多少件

算法设计:

采用动态规划的方法解出此题:

  1. 部分最优则整体最优。

    从背包只放入一种物品开始,每次背包容量加一,并在该容量判断背包在实现最大价值的情况下,最多可以加入该物品多少个。显然符合动态规划部分最优全局最优规则

  2. 动规递推入口

    即当背包内物品种类为零时,任意容量价值均为零

    当背包容量为零时,物品种类所对应价值均为零

    从背包有一种物品,背包容积为最大容积开始递推。

  3. 动规方程式

    v[i][j] = max(v[i][j] , v[i][j – weight[i]k] + value[i]k);

  4. 复杂度分析:

    • 定义数组以及价值初始化

      首先,定义结构体,包含物品价格以及每种物品放入价格。由于使用C++的vector结构,故省去C语言初始化线性时间n;

    • 对存放物品个数计数的数组进行初始化,需花费n^m时间

    • 使用三重循环,按照背包内装有几种物品、对应背包容量、放几个对应物品,对表进行递推运算,此时时间复杂度为n^3
    • 总结:时间复杂度为O(n^3),但要比三维数组的时间复杂度以及空间复杂度小

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef struct{
int value = 0;
vector<int> numbers ;
}pacage;
int string_to_number(string s){
stringstream ss(s) ;
int a = 0 ;
ss >> a ;
return a ;
}
//------------------------------------------------------
int main(int argc, char const *argv[])
{
ifstream in("package.txt");
int m = 0 , n = 0 ; // 背包容积、物品种类
string s ;
getline(in,s);
m = string_to_number(s);
s.clear();
getline(in,s);
n = string_to_number(s);
//------------------------------------------------------
vector<int> value(n+1); // 每种物品的价值
vector<int> weight(n+1); // 每种物品一个重量
vector<int> number(n+1); // 每种物品数量
vector< vector<pacage> > v(n+1) ; // 物品总价值
for(int i = 0 ; i <= n ; ++i){v[i].resize(m+1);}
for(int i = 1 ; i <= n ; ++i) {s.clear();getline(in,s); value[i] = string_to_number(s); }
for(int i = 1 ; i <= n ; ++i) {s.clear();getline(in,s); weight[i] = string_to_number(s); }
for(int i = 1 ; i <= n ; ++i) {s.clear();getline(in,s); number[i] = string_to_number(s); }
//------------------------------------------------------
//限制背包
for(int i = 0 ; i <= n ; ++i){
for(int j = 0; j <= m ; ++j) { v[i][j].numbers.resize(100);}
}
for(int i = 1 ; i <= n ; ++i){
for(int j = m ; j >= 0 ;--j){
for(int k = 0 ; k <= number[i] ; ++k){
if(j < k*weight[i]) {break;}
if( v[i][j].value < v[i-1][j-weight[i]*k].value + value[i]*k)
{
for(int s = 0 ; s < 100 ; ++s) { v[i][j].numbers[s] = v[i-1][j-weight[i]*k].numbers[s]; }
v[i][j].value = v[i-1][j-weight[i]*k].value + value[i]*k;
v[i][j].numbers[i] = k ;
}
}
}
}
cout << "背包最优的价值情况"<<endl;
cout << "物品编号 物品数量 物品价值 单个物品体积"<<endl;
for(int i = 1 ; i <= n ; ++i){cout<<" "<<i<<" "<<v[n][m].numbers[i] <<" "<<value[i] << " "<<weight[i]<<endl;}
cout << "背包内物品最高价值"<<endl;
cout << v[n][m].value;
return 0;
}

谢谢访问