Codeforce 632E(가방 변형)

링크:클릭하여 링크 열기
제목: n개 물품의 가치를 제시하고, 각 물품은 임의의 횟수를 선택할 수 있으며, 모든 가치를 적절하게 k회 선택할 수 있는 상황을 구한다.
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INF=0x3f3f3f3f;
int a[1005],dp[1000005];
int main(){
    int n,m,i,j,tmp;
    while(scanf("%d%d",&n,&m)!=EOF){
        tmp=INF;
        for(i=1;i<=n;i++){                      //dp       ，                           
        scanf("%d",&a[i]);                      //            ，   i  
        tmp=min(tmp,a[i]);                      //   
        }
        for(i=1;i<=n;i++)
        a[i]-=tmp;
        memset(dp,INF,sizeof(dp));
        dp[0]=0;
        for(i=0;i<=1000000;i++){
            for(j=1;j<=n;j++)
            if(i>=a[j])
            dp[i]=min(dp[i],dp[i-a[j]]+1);
        }
        for(i=0;i<=1000000;i++)
        if(dp[i]<=m)
        printf("%d ",i+tmp*m);                  //       
        printf("
");
    }
    return 0;
}