题目描述

一个小偷向一家商店走去，像往常一样，他带着他的幸运背包。背包可以装 k 件商品。在商店里有 n 种商品，每种商品有无数件，商品价格为 $a_iai。小偷比较贪心，他总会选择 k 件商品装满背包（同一种商品可以多次装入）。$

请找到选择 k 件商品的所有可能价值。

输入格式

第一行两个整数 n, k，表示 n 种商品，背包容量 k。

第二行 n 个整数

输出格式

输出所有可能被盗商品的总价值，由一个空格隔开。这些数字应按升序排列。

样例1

输入

3 21 2 3

输出

2 3 4 5 6

样例2

输入

5 51 1 1 1 1

输出

样例3

输入

3 33 5 11

输出

9 11 13 15 17 19 21 25 27 33

数据范围

对于 30%的数据，1

对于 100%的数据，1

限制

2s, 256M

还是有点意思的，一开始只做了n^4的方法。正解是将所有数排序减去最小数之后背包，最后判断个数是否小于K直接加上K*min（最小价值）就行了,因为减去的可以用最小值去补，最终一定能补到K个,复杂度是（n^3）。

代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define LL long long  7 using namespace std; 8 template 
          
            inline void read(_T &_x){ 9 int _t;bool _flag=false;10 while((_t=getchar())!='-'&&(_t<'0'||_t>'9'));11 if(_t=='-')_flag=true,_t=getchar();_x=_t-'0';12 while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';13 if(_flag)_x=-_x;14 }15 const int maxn=505;16 int n,x,ct,K,lm,a[maxn];17 int dp[maxn*maxn];18 bool vis[maxn];19 read(n),read(K);20 for(register int i=1;i<=n;++i){21 read(x);22 if(!vis[x]){ 23 vis[x]=1;24 a[++ct]=x;25 }26 }27 n=ct;28 sort(a+1,a+n+1);29 for(int i=2;i<=n;++i){30 a[i]-=a[1];31 }32 lm=a[n];33 lm=lm*K;34 memset(dp,0x3f3f,sizeof dp);35 dp[0]=0;36 for(register int i=n;i>=2;--i){37 for(register int j=a[i];j<=lm;++j)38 dp[j]=min(dp[j],dp[j-a[i]]+1);39 }40 if(lm==0)printf("0");41 else {42 for(int i=0;i<=lm;++i)43 if(dp[i]<=K)printf("%d ",i+a[1]*K);44 }45 return 0;46 }47

转载于:https://www.cnblogs.com/AT-HENS/p/7767339.html

你可能感兴趣的文章