0-1背包问题_有 n 件物品,第 i 件物品的重量为 (整数)。 对于给定的整数 w, 请选择一些物品,使



描述：
需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。

输入：
多个测例，每个测例的输入占三行。第一行两个整数：n（n<=10）和c，第二行n个整数分别是w1到wn，第三行n个整数分别是p1到pn。
n 和 c 都等于零标志输入结束。

输出：
每个测例的输出占一行，输出一个整数，即最佳装载的总价值。

输入样例：
1 2

1

1

2 3

2 2

3 4

0 0
输出样例：
1

4

#include<iostream>

using namespace std;

int n,c;
int w[10];
int p[10];
int a[10];
int b[10000];
int g=0;
int q;
int search(int m);

int main()
{
 int i,j;
 int d[100];
 
 for(;;)
 {
  q=0;
  cin>>n>>c;
  if(n==0&&c==0)
  {
   break;
  }
  for(i=0;i<n;i++)
  {
   cin>>w[i];
  }
  for(i=0;i<n;i++)
  {
   cin>>p[i];
  }
  search(0);
  for(i=0;i<q-1;i++)
  {
   if(b[i]>b[i+1])
   {
    b[i+1]=b[i];
   }
  }
  d[g]=b[q-1];
  g++;
 }
 for(i=0;i<g;i++)
 {
  cout<<d[i]<<endl;
 }
}
int search(int m)
{
 int sum1;
 int sum2;
 int i;
 if(m==n)
 {
  sum1=0;
  sum2=0;
  for(i=0;i<n;i++)
  {
   if(a[i]==1)
   {
    sum1=sum1+w[i];
    sum2=sum2+p[i];
   }
  }
  if(sum1<=c)
  {
   b[q]=sum2;
   q++;
  }
 }
 else
 {
  for(i=0;i<2;i++)
  {
   a[m]=i;
   search(m+1);
  }
 }
}