湘潭大學OJ1198Candy(01背包)

題目描述

Henry和Lena最近買了很多各種各樣的糖…他們決定把所有糖分了… 但是兩個人都不希望自己糖的總重量比對方少太多， 鑒於不同的糖的味道不盡相同，所以每個糖都有一個yummy值。 Henry希望知道在兩人得到的糖總質量差不大於m的時候，自己的糖yummy值之和的盡量大。

輸入

有多組數據 每組數據第一行為兩個整數，n，m，(1 <=n <= 100， 0 <= m <= 500) 接下來有兩行，每行有n個數，第一行的第i個數表示第i顆糖的重量xi（ 0 < xi <= 100）， 第二行的第i個數表示第i顆糖的yummy值 yi( 0 < yi <= 100 )

輸出

每行輸出一組數據的結果， 一個數表示Henry的糖的總yummy值的最大值，如果不存在如題所述的分糖方案，輸出-1

樣例輸入

1 30
43
15
2 290
89 22
76 77

樣例輸出

-1
153

Source

WCY

#include
int abs(int a)
{
    return a>0?a:-a;
}
int main()
{
    int n,m,dp[100005],W,w[105],v[105];
    while(scanf("%d%d",&n,&m)>0)
    {
        W=0;
        for(int i=0; i=w[i]; tw--)
        if(dp[tw]=0)
            dp[tw]=dp[tw-w[i]]+v[i];

        int max=-1;
        for(int tw=W; tw>0; tw--)
        if(dp[tw]>max&&abs(W-2*tw)<=m)
            max=dp[tw];

        printf("%d\n",max);
    }
}