关键词：
背包问题
- 描述
- 现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
- 输入
- 第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；
随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。 - 输出
- 输出每组测试数据中背包内的物品的价值和，每次输出占一行。
- 样例输入
-
1 3 15 5 10 2 8 3 9
- 样例输出
-
65
#include <iostream>
#include <algorithm>
using namespace std;typedef struct
int v,w;
goods;bool cmp(goods g1,goods g2)
return g1.v>g2.v;int main()
int n;
cin>>n;
while(n--)
int s,m;
cin>>s>>m;
goods g[11];
for(int i=0;i<s;i++)
cin>>g[i].v>>g[i].w;
sort(g,g+s,cmp);
int sum=0;
for(int i=0;i<s;i++)
if(m<0) //背包没有剩余的空间时，跳出循环
break;
if(m>=g[i].w) //背包剩余的重量比当前货物的重量的大时，
sum+=(g[i].w*g[i].v);
m-=g[i].w;
else if(m<g[i].w) //背包剩余的重量比当前货物的重量小时
sum+=(m*g[i].v);
m-=m;
cout<<sum<<endl;
return 0;
nyoj49-开心的小明(动态规划，0-1背包问题)(代码片段)
49-开心的小明内存限制:64MB时间限制:1000msSpecialJudge:Noaccepted:7submit:11题目描述:小明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买... 查看详情
题解报告：nyoj#311完全背包（恰好装满）(代码片段)
描述：直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。本题要求是背... 查看详情
nyoj1091还是01背包(超大数)(代码片段)
nyoj1091还是01背包描述有n个重量和价值分别为wi和vi的物品，从这些物品中挑选总重量不超过W的物品，求所有挑选方案中价值总和的最大值1<=n<=401<=wi<=10^151<=vi<=10^151<=W<=10^15分析：在做的时候毫无头绪，在网上看... 查看详情
nyoj49开心的小明(01背包问题)
时间限制：1000 ms | 内存限制：65535 KB难度：4描写叙述小明今天非常开心。家里购置的新房就要领钥匙了，新房里有一间他自己专用的非常宽敞的房间。更让他高兴的是。妈妈昨天对他说：“你的房间须要购买哪些... 查看详情
nyoj311完全背包
完全背包时间限制：3000 ms | 内存限制：65535 KB难度：4 描述直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使... 查看详情
nyoj311完全背包
完全背包时间限制：3000 ms | 内存限制：65535 KB难度：4描述直接说题意，完全背包定义有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是c，价值是w。求解将哪些物品装入背包可使这些... 查看详情
nyoj860又见01背包(背包变形）
题目860题目信息执行结果本题排行讨论区又见01背包时间限制：1000 ms | 内存限制：65535 KB难度：3描写叙述 有n个重量和价值分别为wi和vi的物品。从这些物品中选择总重量不超过W 的物品，求全... 查看详情
nyoj860又见01背包
又见01背包时间限制：1000 ms | 内存限制：65535 KB难度：3描述 有n个重量和价值分别为wi和vi的物品，从这些物品中选择总重量不超过W 的物品，求所有挑选方案中物品价值总和的最大值。 1<... 查看详情
nyoj会场安排问题(代码片段)
#include<iostream>#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>usingnamespacestd;structHYintu,v;hy[10005];boolcmp(HYa,HYb)if(a.v==b.v)returna.u 查看详情
nyoj203三国志（最短路加01背包）
三国志时间限制：3000 ms | 内存限制：65535 KB难度：5 描述《三国志》是一款很经典的经营策略类游戏。我们的小白同学是这款游戏的忠实玩家。现在他把游戏简化一下，地图上只有他一方势力，现在他只有一个... 查看详情
部分和问题nyoj(代码片段)
部分和问题时间限制：1000 ms | 内存限制：65535 KB难度：2 描述给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。 输入首先，n和k，n表示数的个数，k表示数的和。接着一行n个数... 查看详情
布线问题(nyoj38)(代码片段)
布线问题时间限制：1000 ms | 内存限制：65535 KB难度：4 描述南阳理工学院要进行用电线路改造，现在校长要求设计师设计出一种布线方式，该布线方式需要满足以下条件：1、把所有的楼都供上电。2、所用... 查看详情
nyoj14-会场安排问题(贪心)(代码片段)
14-会场安排问题内存限制:64MB时间限制:3000msSpecialJudge:Noaccepted:9submit:15题目描述:学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动... 查看详情
nyoj22-素数求和问题(打表)(代码片段)
22-素数求和问题内存限制:64MB时间限制:3000msSpecialJudge:Noaccepted:41submit:52题目描述:现在给你N个数（0<N<1000），现在要求你写出一个程序，找出这N个数中的所有素数，并求和。输入描述:第一行给出整数M(0<M<10)代表多少组测... 查看详情
背包问题(代码片段)
文章目录0-1背包问题完全背包问题多重背包问题多重背包问题1多重背包问题2组合背包问题组合排列dp数组初始化问题背包问题代码模板和leetcode相关例题参考0-1背包问题一件物品，只有选和不选两种情况，也就是每件物... 查看详情
背包问题(代码片段)
背包问题分类：0-1背包（每种物品只有一个）完全背包（每种物品无限多）多重背包（每种物品Mi个，0-1背包算是多重背包的特殊情况）混合背包。。。解决此类问题主要将其转化为0-1背包的问题&#x... 查看详情
背包问题(代码片段)
文章目录0-1背包问题完全背包问题多重背包问题多重背包问题1多重背包问题2背包问题代码模板和leetcode相关例题参考0-1背包问题一件物品，只有选和不选两种情况，也就是每件物体，最多选一次；优化空间。if(v[i... 查看详情