第十九届西南科技大学ACM程序设计竟赛 (同步赛)

E

• 01背包的变形，背包的容量是所有数字的总和，然后从数组中选择适当的元素放入背包，价值和代价都是元素的值。f[x]是x容量下最多可以装多少东西。题目要求装的东西的量各不相同，所以最后需要用set去重。

• 不去重的话结果如图

  

代码：

#include "bits/stdc++.h"
using namespace std;
int a[1005],f[10005];
set<int>s;
int main(){
    int n;
    cin>>n;
    int idx=0,sum=0,ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=1;i<=n;i++)
        for(int j=sum;j>=a[i];j--){
            f[j]=max(f[j],f[j-a[i]]+a[i]);
        }
    for(int i=1;i<=sum;i++){
        if(f[i]) {
            s.insert(f[i]);           //去重
//         cout<<f[i]<<endl;
        }
    }
    cout<<s.size();
    return 0;
}

Donate