题目是北航CG上的题，完全背包练习题。

写这篇文章主要是觉得这个题比较有特点，在求最优解之外还要求标记函数和最后放置的物品是什么。

作为一个算法菜鸡加python初学者，我写了好久才搞定，如果我的程序有问题欢迎指正。

【问题描述】用动态规划算法求解整数背包（完全背包）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    1    1    2    2    3    3    4    4    5

F[ 2 ]:     0    1    3    3    4    6    6    7    9    9

F[ 3 ]:     0    1    3    5    5    6    8   10   10   11

F[ 4 ]:     0    1    3    5    5    6    9   10   10   12

i[ 1 ]:     0    1    1    1    1    1    1    1    1    1

i[ 2 ]:     0    1    2    2    2    2    2    2    2    2

i[ 3 ]:     0    1    2    3    3    2    3    3    3    3

i[ 4 ]:     0    1    2    3    3    2    4    3    3    4

[0, 1, 0, 1]

【样例说明】

输入数据第一行是物品种类数n；

第2到n+1行是每一种的物品的重量（整型数）、空格、价值（整型数）；

第n+2行是背包的（重量）容量（整型数）。

输出为背包实例的输出数据初始值（即未调用动态规划的初始值）

提示：格式输出可参考 cout << setw(5) << F[i][j]; // setw(5) 设置栏宽5位，默认右对齐

我的思路

首先是传统的完全背包状态转移方程式，我这里只是最基本的公式，还可以继续通过数组压缩等方式优化。

dp[i][j]  =  dp[i-1][j]                                        ，j<w[j]

dp[i][j]  =  max（dp[i-1][j]，dp[i][j-w[i]]+v[j]），j>=w[j]

这样就解决了题目要求的第一部分：优化函数表。

然后是标记函数表，这里我用二维列表f表示，f的状态转移方程式为。

f[i][j]  =  f[i-1][j]                 ，j<w[j]

f[i][j]  =  i                          ，j>=w[j]，dp[i][j-w[i]]+v[j]>dp[i-1][j]

f[i][j]  =  f[i-1][j]                 ，j>=w[j]，dp[i][j-w[i]]+v[j]>dp[i-1][j]

注：这个公式是自己推的，在我的程序跑没问题。

这样在原先推dp的循环上加入了f的推导，在同一个循环实现推出f

最后剩下了最优情况的物品个数，一开始我打算用三维数组解决，但是又觉得这个方法实在太笨了，于是我想到了用数位表示每个数的个数，二维列表用ending[]表示

（虽然这样有局限性，例如我的程序中使用了每个十分位表示一个个数，这样表示的上限是放置9个物品，我提交的时候发现过了，说明测试数据都没超过九，大家可以根据需求改为每百分位或千分位表示一个物品，这样准确度更高）

下面是状态转移方程式：

ending[i][j]=ending[i - 1][j]                 ，j<w[j]

ending[i][j]=ending[i][j - w[i]] + pow(10,i-1)，j>=w[j]，dp[i][j-w[i]]+v[j]>dp[i-1][j]

ending[i][j]=ending[i - 1][j]                 ，j>=w[j]，dp[i][j-w[i]]+v[j]>dp[i-1][j]

注：这个公式是自己推的，在我的程序跑没问题。

下面放代码，没有注释，思路都在上面的文章里啦~

哦对了，这个题卡输出格式非常严格，输出数组的时候要每位占5个字符，最后提交的时候卡了我好几遍。

n = int(input())
w = [0]
v = [0]

for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)
b = int(input())
dp = [[0] * (b + 1) for _ in range(len(v))]
f = [[0] * (b + 1) for _ in range(len(v))]
ending = [[0] * (b + 1) for _ in range(len(v))]
for i in range(1, len(v)):
    print('F[ {a} ]: '.format(a=i), end='')
    for j in range(1, b + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
            f[i][j] = f[i - 1][j]
            ending[i][j] = ending[i - 1][j]
        else:
            dp[i][j] = max(dp[i][j - w[i]] + v[i], dp[i - 1][j])
            if dp[i][j - w[i]] + v[i] > dp[i - 1][j]:
                f[i][j] = i
                ending[i][j] = ending[i][j - w[i]] + pow(10,i-1)
            else:
                f[i][j] = f[i - 1][j]
                ending[i][j] = ending[i - 1][j]
        print('{num:5}'.format(num=dp[i][j]), end='')
        if j == b:
            print('')

for i in range(1, len(v)):
    print('i[ {a} ]: '.format(a=i), end='')
    for j in range(1, b + 1):
        print('{num:5}'.format(num=f[i][j]), end='')
        if j == b:
            print('')
# for i in range(0, len(v)):
#     print('')
#     for j in range(0, (b + 1)):
#         print(ending[i][j], end=' ')
#         if j == b:
#             print('')
e = int(ending[len(v)-1][b])
ll = []
while e>0:
    ll.append(int(e%10))
    e = int(e/10)
print(ll,end='')