// 0-1背包问题求解，及输出路径和选择的物品
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
int main()
{
const int objNum = 4;
const int rom[objNum + 1] = {0, 2, 3, 4, 5}; // 物品占用空间
const int val[objNum + 1] = {0, 3, 4, 5, 3}; // 物品价值
int res[objNum + 1] = {0}; // 选择的物品
const int maxRom = 8; // 背包空间
int dp[maxRom + 1] = {0}; // 记录动态规划路径表
//FORCE_FULL 1 时是打开时求的是刚好装满的情况， 并且如果 dp[maxRom] < 0 时说明没有刚好装满的情况
#define FORCE_FULL 0
#if FORCE_FULL
for (int i = 1; i <= maxRom; i++) {
dp[i] = -99; //初始化一个比最大物品还大的数，并取负
}
#endif
int path[objNum + 1][maxRom + 1] = {0};
for (int i = 1; i <= objNum; i++) {
for (int j = maxRom; j >= rom[i]; j--) {
int tmp = dp[j - rom[i]] + val[i];
if (tmp > dp[j]) {
dp[j] = tmp;
path[i][j] = 1;
printf("%5d", path[i][j]);
}
}
cout << endl;
}
cout << dp[maxRom] << endl;
#if FORCE_FULL
if (dp[maxRom] < 0) {
cout << "error, not full" << endl;
}
#endif
// output res
for (int j = maxRom, i = objNum; j >= 0 && i >= 0; i--) {
printf("--path[%d][%d] = %5d\n", i, j, path[i][j]);
if (path[i][j] > 0) {
res[i] = 1;
j -= rom[i];
}
}
cout << endl;
for (int i = 1; i <= objNum; i++) {
printf("%5d", res[i]);
}
cout << endl << "===============" << endl;
return 0;
}
/*
运行结果：
1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1
9
--path[4][8] = 0
--path[3][8] = 1
--path[2][4] = 1
--path[1][1] = 0
--path[0][1] = 0
0 1 1 0
===============
*/
