- 问题描述
- 算法实现
- 结果
01背包问题
问题分析
- 动态规划法分析:1.划分子问题,2.得出子问题的递推公式,3.填表
- 划分子问题
- 用数组V[n][n]存储价值和重量关系,行表示物体,列表示重量
- 第0行和第0列设置为0,没有物体的时候价值没0,重量为0的时候物体无论多少价值也为0
- 如果第i个物体重量小于当前总重量j,则取前i-1和第i个物体组合的最优值,否则该物体不可以放进背包,取前i-1个物体的最优价值
- 递推公式
- 不装入背包时:V(i-1, j) j < wi
- 装入背包时:max{V(i-1, j), V(i-1, j-wi)+vi } j >= wi
- V(i-1, j-wi)+vi 表示用当前值和子问题的解结合,取最优
- 填表
#include
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<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
结果
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)