confusion on a simple dp problem

Правка en4, от DNNJFM, 2016-08-11 07:45:42

the dp problem: stamp

I try to use dp in the following way, but get wrong on test 9, my method is:

let dp[i][j] be the max value W that can be made from 1 to W, with the condition that we use first i types of coin and at most j coins to make the total value. then anwser is dp[N][K].

for(int i=1;i<=N;i++)for(int j=0;j<=K;j++)
    {
        long long maxlen=dp[i-1][j];
        long long k=1;
        while(k<=j){
            int next= k * a[i];
            if(next>maxlen+1)break;
            else{
                maxlen=max(maxlen,k*a[i]+dp[i-1][j-k]);
                k++;
            }
        }
        dp[i][j]=maxlen;
    }
    
fout<<dp[N][K]<<endl;

it wrong for test case: K(max coin to use)=6, N(size of coins set)=10 , coins={1 2 9 31 255 480 4 15 63 127 } my output is 242,while anwser is 720.

I try hard, but I can't figure out why this method is wrong. Anyone please take a minute to help me with this simple dp problem, thank you so much in advance!

Теги simple dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский DNNJFM 2016-08-11 17:37:25 223
en6 Английский DNNJFM 2016-08-11 09:11:42 0 (published)
en5 Английский DNNJFM 2016-08-11 09:08:51 30 Tiny change: 'with this simple dp proble' -> 'with this dp proble' (saved to drafts)
en4 Английский DNNJFM 2016-08-11 07:45:42 0 (published)
en3 Английский DNNJFM 2016-08-11 07:39:42 36
en2 Английский DNNJFM 2016-08-11 07:38:51 56 (saved to drafts)
en1 Английский DNNJFM 2016-08-11 07:36:03 1073 Initial revision (published)