1103 Integer Factorization

题目描述
知识点： 二维完全背包
思路： 本题跟Find Mode Coins很像，也是背包问题。但是本题与另外一题的区别是状态属性不一样：本题的状态属性是凑出来的和最大值。但是另外一题仅仅为能否凑出的true与false。因为本题如果那样表示的话，确实可以保证字典序最大或者最小，但是无法保证和最大。有可能是一个很大的数字加上很小的数字，这样的字典序是最大的，但是和很小。

实测写过那样的代码，跑出来的结果为：169 = 12^2 + 4^2 + 2^2 + 2^2 + 1^2
与169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2不一样。确实保证了字典序最大，但是不是和最大。

所以，需要将状态属性修改，表示为和最大，把每个数字看成取它的价值，数字的p次方看成花费，另外取的个数是容量（另一维度限制）
另外完全背包的状态转移公式为
f[i][j][k] = max( f[i-1][j][k],f[i-1][j-w[i]][k-1]+v[i], f[i-1][j-2 * w[i]][k-2]+2 * v[i],…+f[i-1][j-c * w[i]][k-c]+c * v[i]
f[i][j-w[i]][k-1] = max(f[i-1][j-w[i]][k-1],f[i-1][j-2*w[i]][k-2]+v[i]+…+f[i-1][j-c * w[i]][k-c]+(c-1) * v[i])
进行等价替换得 f[i][j][k] = max(f[i-1][j][k],f[i][j-w[i]][k-1]+v[i])

f[i][j][k]表示从前i个物品中选背包体积为j，并且已经选了k个物品的最大和的所有方案集合。

在保证和最大得情况下如何保证输出得字典序最大？
因为我们需要倒序输出，往前反推回去。如果当前取这个物品的最优解情况比不取这个最优解是 大于等于 的话，就输出它。

等于是因为最优解的sum存在多种情况，但是因为要字典序最大，尽可能取这个值。

#include
#include
#include
#include
const int N = 410;
typedef long long ll;
int f[20+3][N+3][N+3];
using namespace std;
int main(){
    int n,p,k;
    cin>>n>>k>>p;
    int m;//表示有的物品个数
    memset(f,-0x3f,sizeof f);
    f[0][0][0] = 0;
    for(m = 1;;m++){
        if(pow(m,p) > n) break;
        for(int j = 0;j <= n;j++){
            for(int c = 0;c <= k;c++){
                f[m][j][c] = f[m-1][j][c];
                if(pow(m,p) <= j && c > 0)
                    f[m][j][c] = max(f[m][j][c],f[m][j-(int)pow(m,p)][c-1] + m);
            }
        }
    }
    m--;
    if(f[m][n][k] < 0){
        cout<<"Impossible";
        return 0;
    }
    bool is_first = true;
    printf("%d =",n);
    while(m){
        int w = pow(m,p);
        while(f[m][n-w][k-1]+m >= f[m-1][n][k]){//这个物品可以被取多次，所以循环
            if(is_first)
                printf(" %d^%d",m,p);
            else printf(" + %d^%d",m,p);
            is_first = false;
            n-=w;
            k--;
        }
        m--;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45