VIP de Programming

[今週の問題]最適な数量の組み合わせ[解答]

http://vipprog.tumblr.com/post/32323189 の解答です。
241：[sage]： 2008/04/21(月) 00:03:59.76 ID:MVpGAsh50 (2)

>>99>>100の解説ですっ  
有名なナップサック問題っていう問題で、値がすべて整数であることと、  
合計値が大して大きくないことを利用して、動的計画法で解きますっ  

自分説明下手っぽいからソース読んだほうがわかりそうなので  
ソース投下しておきますねｗ

#include<stdio.h>
int dp[100001];
int main(){
    int cost[20],weight[20],i,j,k,n,wmax,result = 0;
    scanf("%d %d",&wmax,&n);
    for(i=0;i<n;i++)
        scanf("%d",&weight[i]);
    for(i=0;i<n;i++)
        scanf("%d",&cost[i]);
    dp[0]=1;
    for(i=0;i<n;i++)
        for(j=wmax-1;j>=0;j--){
            if(dp[j]==0)
                continue;
            for(k=1;k<=10;k++){
                if(j+weight[i]*k>wmax)
                    break;
                if(dp[j+weight[i]*k]<dp[j]+cost[i]*k)
                    dp[j+weight[i]*k]=dp[j]+cost[i]*k;
            }
        }
    for(i=wmax;i>=0;i--)
        if(result<dp[i])
            result = dp[i];
    printf("%d",result-1);
    return 0;
}