7、背包问题
【问题描述】
简单的背包问题。设有一个背包，可以放入的重量为s。现有n件物品，重量分别为w1,w2…，wn，（1≤i≤n）均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。找到一组解即可。
【输入格式】
第一行是物品总件数和背包的载重量，第二行为各物品的重量。
【输出格式】
各所选物品重量。
【输入样例】
5 10
1 2 3 4 5
【输出样例】
number:1 weight:1
number:4 weight:4
number:5 weight:5

#include<iostream>
using namespace std;
int k(int s,int n,int a[])
{if(s==0){return (1);}else{if(s<0||(s>0&&n<1)){return (0);}else{if(k(s-a[n-1],n-1,a)){cout<<"number:"<<n<<"  "<<"weight:"<<a[n-1]<<endl;return (1);}else{return k(s,n-1,a);}}}}
int main()
{int S,n,a[100],t;cin>>n>>S;for(int i=0;i<n;i++)cin>>a[i];t=k(S,n,a);if(t==0)cout<<"not found"<<endl;
}