题目

点击显/隐题目

Rbb和蕊蕊要出去比赛,他们需要带很多东西,但是他们只有一个背包。为了能够尽可能多带一些重要的东西,现在他们找你来帮忙。
为了简化问题,我们将其简化成简单的数学模型。将n个价值为w_i,体积为c_i的物品,放入一个容量为v的背包。显然,我们需要满足Σc_i≤v,同时Σw_i尽可能大。


第1行:T。数据组数(0≤n≤10)
第1行:n,v。 物品的个数(0≤n≤10),背包容量(0≤v≤1000000000)
第2~n+1行:w_i,c_i。第i个物品的价值(0≤w_i≤1000)和体积(0≤w_i≤100000000)


在一行内输出一个整数,表示背包内能装入的物品最大的价值和


1
5 10
1 2
1 3
2 2
2 3
3 4


7

题解

体积比较大而物品个数比较小,可以直接用dfs求解

代码

点击显/隐代码
背包装物代码备份
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 15;
int ans = -1;
int n,v;
int w[maxn],c[maxn];
int dfs(int i,int value,int weight){
if(weight<0)
return max(ans,value-w[i-1]);
if(i>=n)
return value;
return max(dfs(i+1,value+w[i],weight-c[i]),dfs(i+1,value,weight));
}
int main(){
//freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&v);
for(int i=0;i<n;++i)
scanf("%d%d",&w[i],&c[i]);
printf("%d\n",dfs(0,0,v));
}
return 0;
}