Charm Bracelet（01背包问题）

题目链接：

题目描述：

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N≤ 3,402) available charms. Each charm i in the supplied list has a weight W_i(1 ≤ W_i ≤ 400), a 'desirability' factor D_i (1 ≤ D_i ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers:W_i and D_i

Output

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

Sample Output

23
题意描述：
输入物品的数量和限重
计算并输出在此限重下，能获得的最大价值
解题思路：
问题 在N件物品中挑选，重量不超过M的情况下，能获得的最大价值是多少
抽象问题也是当前状态为 从前i件物品中挑选，重量不超过j的情况下，能获得的最大价值是多少
变量 i j
对于每件物品，有两种不同的取法，取，则下一个问题变为从前i-1件物品中挑选，重量不超过j-w[i]的情况下，能做的的最大价值是多少
　　　　　　　　　　　　　　　　不取，则下一个问题变为从前i-1件物品中挑选，重量不超过j的情况下，能做的最大价值是多少
那么归结状态转移方程为：
f[i][j]= max(f[i-1][j-w[i]]+d[i],f[i-1][j]) 当i>1
　　　　　0　　　　　　　　　　　　　　　　　　  当i=1且j<w[1]
　　　　　w[1]　　　　　　　　　　　　　　　　  当i=1且j>=w[1]
由于存储数据的是二维数组，当N*M特别大的时候，往往出现超时错误，又发现结果可以用一个一维数组存储,因为f[i][j]的值只和它正上方的元素以及左上方的元素有关，换句话说就是
每一个问题的下一个问题都是从i-1件物品中取，从而考虑将i这个变量去掉。
如果能将求出的f[i][j]的值放在f[i-1][j]里面，则f数组就可以使用一维数组代替了。考虑如果从左往右计算，
f[i-1][j]的值先比f[i][j]的值先更新，而f[i-1][j]的值在求之后的f[i][k](k>j)的值的时候用到，所以不能从左往右。考虑从右往左计算，也就是先用大的限重去装，也不影响最后结果
的正确性。故采用滚动数组如下

for(i=;i<=n;i++)

            for(j=m;j>=;j--)

                if(a[i].w <= j)

                    f[j]=max(f[j],f[j-a[i].w]+a[i].d);

代码实现:

    #include<stdio.h>

struct node{

    int w,d;

};

int max(int x,int y){

    return x>y?x:y;

}

int main()

{

    int n,m,i,j;

    struct node a[];

    int f[];

    while(scanf("%d%d",&n,&m) != EOF)

    {

        for(i=;i<=n;i++)

            scanf("%d%d",&a[i].w,&a[i].d);

        for(i=;i<=m;i++)//初始化，在前1种物品中选取，在体积不超过i的情况下所能获得的最大价值

            if(a[].w<=i)

                f[i]=a[].d;

            else

                f[i]=;

        for(i=;i<=n;i++)

            for(j=m;j>=;j--)

                if(a[i].w <= j)

                    f[j]=max(f[j],f[j-a[i].w]+a[i].d);

        printf("%d\n",f[m]);

    }

    return ;

}

秒客网

Charm Bracelet（01背包问题）

相关文章