Блог пользователя DNNJFM

Автор DNNJFM, история, 8 лет назад, По-английски

the dp problem: stamp Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created.

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 dp problem, thank you so much in advance!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could you share the full source code so i can test it in my machine? ._.

anyways, by looking at it, try this test case: N=2 K=3

arr={1,3}

answer should be 5