背包问题（动态规划）

#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