题目描述

选取“和不超过S”的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。

输入格式

输入一个正整数S，1≤S≤1000。

输出格式

输出最大的约数之和。

输入样例

11

输出样例

9

取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。

解法

思路

本题属于背包问题，给出了一个S，既是背包容量，也限定了数值范围，即物品范围，则每个数的约数之和是这个数的价值。所以本题是给定一个容量为s的背包和s种体积为i、价值为“i的约束和”的物品，求能获得的最大价值。

代码

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int s=0;
    int f[1001]={},w[1001]={},v[1001]={};
    
    cin>>s;
    for(int i=1;i<=s;i++){
            w[i]=i;
            for(int j=1;j<i;j++){
                    if(i%j==0)
                       v[i]+=j;
                    }
            }
    for(int i=1;i<=s;i++){
            for(int j=s;j>=i;j--){
                    f[j]=max(f[j],f[j-w[i]]+v[i]);
                    }
            }
    cout<<f[s];
    return 0; 
    }