#include <iostream>
#define N 4//物品种数
#define B 10//总重限制
using namespace std;
int v[N] = {1, 3, 5, 9};//每种物品的单价
int w[N] = {2, 3, 4, 7};//每种物品的单重
int F[N + 1][B + 1];
int S[N + 1][B + 1];//记录最大物品号
//背包问题，线性帧数规划问题，迭代写法
void Knapsack(int n, int y){//对前n个物品选择，总重不超过y
int i, j, temp0, temp1, temp3;
for (i = 1; i <= n; ++i) {
temp3 = w[i - 1];
for (j = 1; j <= y; ++j) {
temp0 = F[i - 1][j];
if (j - temp3 < 0) {
F[i][j] = temp0;
S[i][j] = S[i - 1][j];
} else {
temp1 = F[i][j - temp3] + v[i - 1];
if (temp0 > temp1) {
F[i][j] = temp0;
S[i][j] = S[i - 1][j];
} else {
F[i][j] = temp1;
S[i][j] = i;
}
}
}
}
}
void Track(int n, int y, int *a){
if (y <= 0) return;
int temp = S[n][y];
if (temp == 0) return;
++a[temp - 1];
Track(temp, y - w[temp - 1], a);
}
int main(){
Knapsack(N, B);
cout<<"可以获得的最大价值为："<<F[N][B]<<endl;
int a[N];
for (int i = 0; i < N; ++i)
a[i] = 0;
Track(N, B, a);
for (int i = 0; i < N; ++i)
cout<<"第"<<i<<"种物品装入："<<a[i]<<endl;
/*
for(int i = 0; i <= N; ++i){
for(int j = 0; j <= B; ++j){
cout<<F[i][j]<<'\t';
}
cout<<endl;
}
cout<<endl;
for(int i = 0; i <= N; ++i){
for(int j = 0; j <= B; ++j){
cout<<S[i][j]<<'\t';
}
cout<<endl;
}
*/
return 0;
}
原理参见 屈婉玲老师 算法设计与分析 ORZ
