在动态规划中,有一类经常出现的问题,即0-1背包问题。所谓0-1背包问题,即有n个物品,其每个背包的价值为vi(1<=i<=n),每个物品的重量为wi(1<=i<=n),背包能够放的总重量为c,求放哪几个物品使得物品的总价值最大。
很明显,物品要么放进背包,要么不放进。故称为0-1背包。
我们假设放进了m个物品{x1,x2,...,xm},那么它是满足最优子结构的,即如果这是问题的最优解,那么{x2,...,xm}一定是问题c-wx1的最优解。所以,这道问题可以用动态规划进行求解。
我们可以定义一个数组m[i][j],用它表示背包容量为j,可选物品为i,i+1,...,n时背包问题的最优值。那么我们可以推断出:
当wi>j时,m[i][j]=m[i+1][j],当wi<=j时,m[i][j]=max{m[i+1][j],m[i+1][j-wi]+vi}。
所以求解背包问题的代码如下:
#include<iostream>
#include<algorithm>
using namespace std;
int n;
//计算
void cal(int *v,int *w,int c,int m[6][11]){
int jMax = min(w[n-1]-1,c);
//首先判断第n个
for(int j=0;j<=jMax;j++)
m[n][j] = 0;
for(int j=w[n-1];j<=c;j++)
m[n][j] = v[n-1];
//在判断2~n
for(int i=n-1;i>=1;i--) {
jMax = min(w[i-1]-1,c);
for(int j=0;j<=jMax;j++)
m[i][j] = m[i+1][j];
for(int j=w[i-1];j<=c;j++)
m[i][j] = max(m[i+1][j],m[i+1][j-w[i-1]]+v[i-1]);
}
bool tag[6];
for(int i=n;i>=1;i--){
if(m[i][c]!=0){
tag[i]=true;
c=c-w[i];
} else{
tag[i]=false;
}
}
for(int i=1;i<=n;i++){
if(tag[i]){
cout<<i<<" ";
}
}
}
//背包问题
int main() {
n=5;
int c=10;
int w[5] = {2,2,6,5,4};
int v[5] = {6,3,5,4,6};
int m[6][11];
cal(v,w,c,m);
cout<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
利用动态规划方法求解经典0-1背包问题,仅供参考,欢迎指正
0-1背包问题的完整c++源码 很不错的,有注释,很详细的
0-1背包问题-算法简洁易懂
用回溯法写的0-1背包问题的解决方案,可以输入数据
利用回溯法解0-1背包问题讲解,程序调试VC++6.0通过
完全版分支界限法求解背包问题,易于理解 分支界限法0-1背包问题
回溯法 0-1背包问题 计算机算法设计与分析 回溯法 背包问题
动态规划法解决0-1背包问题,非常实用,课程实验经常用到
0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码0-1背包问题 动态规划源码
0-1背包问题 (C语言编写)
0-1背包问题 动态规划 分支限界 回溯 贪心四种方法
0-1背包问题的实现代码,可直接编译执行,算法经过了两步的优化
如题,动态规划法求解0-1背包问题实验报告 大二算法作业 使用java语言实现 内容框架:问题描述 思路分析 实例分析 实验原码及运行结果 实验心得
C++ 0-1背包问题源代码
分支界限法实现0-1背包问题,比较清楚明了
算法(c++)——0-1背包问题
遗传算法求解0-1背包问题matlab代码
0-1背包问题 0-1背包问题 0-1背包问题 0-1背包问题