又见01背包

旧城等待， 2022-07-12 10:22 173阅读 0赞

## 又见01背包 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 3

描述

有n个重量和价值分别为wi 和 vi 的 物品，从这些物品中选择总重量不超过 W

的物品，求所有挑选方案中物品价值总和的最大值。

1 <= n <=100

1 <= wi <= 10^7

1 <= vi <= 100

1 <= W <= 10^9

输入

多组测试数据。  
每组测试数据第一行输入，n 和 W ，接下来有n行，每行输入两个数，代表第i个物品的wi 和 vi。

输出

满足题意的最大价值，每组测试数据占一行。

样例输入

4 5
    2 3
    1 2
    3 4
    2 2

样例输出

7

#include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 105;
    int dp[10005];
    
    struct res
    {
    	int vi,wi;//vi是单位重量的价值，wi是重量
    }arr[maxn];
    
    int main()
    {
    	int n,sum,w;//有n组测试数据，背包内能装物品的最大价值和为sum
    	while(~scanf("%d%d",&n,&w))
        {
            sum=0;
            for(int i=0;i<n;i++)
            {
                cin>>arr[i].wi>>arr[i].vi;
                sum +=arr[i].vi;
            }
             memset(dp,100,sizeof(dp));
             dp[0] = 0;
    
            for( int i = n-1 ;i>=0 ;i--)
            for( int j = sum;j>=arr[i].vi ;j--)  //  j〉=vi[i] ，注意
            {
                dp[j] = min(dp[j] ,dp[j-arr[i].vi]+arr[i].wi);
            }
            int i;
            for(i = sum;i>=0;)
             if(w>= dp[i])
                break;
             else i--;
             printf("%d\n",i);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关 01背包

01背包题目描述给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个输入的第一行包

爱被打了一巴掌/ 2022年12月04日 04:27/ 0 赞/ 177 阅读

相关又见优先级

最近编写一个程序,其中有下面一句,g\_ucTimeValue\[0\]=0x23，但表示的却是十进制的23，我想使用下句代码将这个十进制的23变成十六进制的0x17，但结果d

梦里梦外;/ 2022年09月30日 06:24/ 0 赞/ 33 阅读

相关又见GCD

![这里写图片描述][20160720211228540] a和c的最大公约数为b，所以a是b的倍数，要求最小的c，一个循环从b+1–a include<stdi

柔情只为你懂/ 2022年09月23日 14:57/ 0 赞/ 193 阅读

相关又见01背包

时间限制：1000 ms | 内存限制：65535 KB | 难度：3 描述有n个重量和价值分别为wi 和 vi 的物品，从这些物品中选择总重量不超过 W 的物品，求

Dear 丶/ 2022年08月05日 05:05/ 0 赞/ 169 阅读

相关又见01背包

又见01背包时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述有n个重量和价值分别为wi 和 vi 的物品，从这些物品

旧城等待，/ 2022年07月12日 10:22/ 0 赞/ 174 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 247 阅读

相关 01背包

> 题目：有一个背包，体积为m，现在给你n个石头，每个石头都有价值和体积，问这个背包可以装下多大价值的石头。 > > 输入： > 第一行两个整数n，m，分别代表石头的个数

╰半夏微凉°/ 2022年06月08日 09:37/ 0 赞/ 210 阅读

相关 01背包

01背包 > 且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ > > 小Ho现在手上有M张奖券，而奖品区有N

水深无声/ 2022年05月31日 06:29/ 0 赞/ 645 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 368 阅读

相关又见 “KMP”

同 [http://blog.csdn.net/shanshanpt/article/details/8679459][http_blog.csdn.net_shanshanp

- 日理万妓/ 2022年03月20日 01:23/ 0 赞/ 298 阅读