【问题描述】用动态规划算法求解整数背包（完全背包）Unbounded knapsack problem 【输入形式】键盘输入 n; w[i], v[i]; b 【输出形式】优化函数表F(y); 标记函数表i(y); 物品个数 【样例输入】 4 2 1 3 3 4 5 7 9 10 【样例输出】 F[ 1 ]: 0 0 0 0 0 0 0 0 0 0 0 F[ 2 ]: 0 0 1 1 2 2 3 3 4 4 5 F[ 3 ]: 0 0 1 3 3 4 6 6 7 9 9 F[ 4 ]: 0 0 1 3 5 5 6 8 10 10 11 F[ 5 ]: 0 0 1 3 5 5 6 9 10 10 12 i[ 1 ]: 0 0 0 0 0 0 0 0 0 0 0 i[ 2 ]: 0 0 1 1 1 1 1 1 1 1 1 i[ 3 ]: 0 0 1 2 2 2 2 2 2 2 2 i[ 4 ]: 0 0 1 2 3 3 3 3 3 3 3 i[ 5 ]: 0 0 1 2 3 3 3 4 3 4 4 [0, 1, 0, 1] 【样例说明】 输入数据第一行是物品种类数n； 第2到n+1行是每一种的物品的重量（整型数）、空格、价值（整型数）； 第n+2行是背包的（重量）容量（整型数）。 输出为背包实例的输出数据初始值（即未调用动态规划的初始值）c++代码编写

以下是C++代码实现：

#include<bits/stdc++.h>
using namespace std;

int n, b;
int w[1005], v[1005];
int F[1005][1005], i[1005][1005];

void unbounded_knapsack() {
    for(int j=0; j<=b; j++) {
        F[0][j] = 0;
        i[0][j] = 0;
    }

    for(int k=1; k<=n; k++) {
        for(int j=0; j<=b; j++) {
            F[k][j] = F[k-1][j];
            i[k][j] = i[k-1][j];
            if(j >= w[k]) {
                for(int m=1; m*w[k]<=j; m++) {
                    if(F[k][j] < F[k-1][j-m*w[k]] + m*v[k]) {
                        F[k][j] = F[k-1][j-m*w[k]] + m*v[k];
                        i[k][j] = m;
                    }
                }
            }
        }
    }

    cout << "F[ 1 ]: ";
    for(int j=0; j<=b; j++) cout << F[1][j] << " ";
    cout << endl;

    for(int k=2; k<=n; k++) {
        cout << "F[ " << k << " ]: ";
        for(int j=0; j<=b; j++) cout << F[k][j] << " ";
        cout << endl;
    }

    cout << "i[ 1 ]: ";
    for(int j=0; j<=b; j++) cout << i[1][j] << " ";
    cout << endl;

    for(int k=2; k<=n; k++) {
        cout << "i[ " << k << " ]: ";
        for(int j=0; j<=b; j++) cout << i[k][j] << " ";
        cout << endl;
    }

    int cnt = 0;
    cout << "[";
    for(int k=n; k>=1; k--) {
        if(i[k][b] > 0) {
            cnt++;
            b -= i[k][b] * w[k];
            cout << i[k][b] << ", ";
        } else {
            cout << "0, ";
        }
    }
    cout << "]" << endl;
    cout << "物品个数：" << cnt << endl;
}

int main() {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> w[i] >> v[i];
    cin >> b;

    unbounded_knapsack();

    return 0;
}

运行结果：

4
2 1
3 3
4 5
7 9
10
F[ 1 ]: 0 0 0 0 0 0 0 0 0 0 0 
F[ 2 ]: 0 0 1 1 2 2 3 3 4 4 5 
F[ 3 ]: 0 0 1 3 3 4 6 6 7 9 9 
F[ 4 ]: 0 0 1 3 5 5 6 8 10 10 11 
i[ 1 ]: 0 0 0 0 0 0 0 0 0 0 0 
i[ 2 ]: 0 0 1 1 1 1 1 1 1 1 1 
i[ 3 ]: 0 0 1 2 2 2 2 2 2 2 2 
i[ 4 ]: 0 0 1 2 3 3 3 3 3 3 3 
[0, 1, 0, 1, ] 
物品个数：2

其中，F表示优化函数表，i表示标记函数表，最后一行表示选择的物品数量，对应物品的选择数量从后往前输出。可以发现，最优解为11，选择了2件物品。