题目

{% fold 点击显/隐题目 %}

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
{% endfold %}

题解

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

代码

{% fold 点击显/隐代码 %}```cpp 背包装物 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
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;
}

{% endfold %}