FZU 2214 Knapsack problem

最新推荐文章于 2018-09-17 18:30:15 发布

炎灸纹武

最新推荐文章于 2018-09-17 18:30:15 发布

阅读量736

点赞数

分类专栏：背包问题文章标签： algorithm

本文链接：https://blog.csdn.net/Seraphimon/article/details/50418204

版权

背包问题专栏收录该内容

6 篇文章

订阅专栏

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2214

题意：给你一个背包，让你往里面尽量加价值总和多的物品。

思路：是个01背包问题，但由于重量过大，所以，我们要反过来求用尽量轻的重量组成一个价值，最后输出要求的。

代码如下：

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
using namespace std;
typedef __int64 LL;

struct node
{
    int w, v;
} vis[600];

LL dp[5600];

int main()
{
    int T;
    scanf ( "%d", &T );
    while( T-- )
    {
        int n, b, v = 0;
        scanf ( "%d %d", &n, &b );
        for( int i = 1; i <= n; i ++ )
            scanf ( "%d %d", &vis[i].w, &vis[i].v ),v += vis[i].v;
        memset( dp, 0x3f3f3f3f, sizeof( dp ) );
        dp[0] = 0;
        for( int i = 1; i <= n; i ++ )
            for( int j = v; j >= vis[i].v; j -- )
            {
                dp[j] = min( dp[j], dp[j-vis[i].v] + vis[i].w );
            }
        for( ; v >= 0; v -- )
           if( dp[v] <= b )
            {
                printf("%d\n", v );
                break;
            }
    }
    return 0;
}