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; }