有n个魔法石，重量分别为w1，w2，w3…wn，有一个可装重量为s的背包，从n件魔法石中取若干件，使得放入背包的重量之和刚好为s，求放的方法，若不存在该种情况则输出failed。 【输入样例】 10（s） 5（n） （重量）1 2 3 4 5 【输出样例】 1 4 5
递归，即一个一个将物品放入背包内试一下，设函数judge(s,n)表示剩下n个物品，需要装入大小为s的包中，如果有解返回1，无解返回0。 1. 取最后一个物品， if(judge(s-wn,n-1)) cout<
#include<iostream>#include<stdio.h>using namespace std;int v;int w[5000]={0};bool judge(int s,int n){ if(n==s) return 1; if(s<0||(s>0&&n<1)) return 0; if(judge(s-w[n],n-1)) { cout<<w[n]<<' '; return 1; } else return judge(s,n-1); //如果装了第n个包无解则删除该包尝试第n-1个 }int main(void){ int n; cin>>v>>n; for(int i=0;i<n;i++) { cin>>w[i]; } if(judge(s,n)) cout<<'/n'; else cout<<"failed"<<endl; return;}其实如果不用打印解的情况的话可以用另外一种方法，也是DP。拿装箱问题为例，（code vs 1014） 先另建一个数组dp[],每读入一个包裹的大小后遍历整个数组，将数组中值为1的下标加上该包裹大小之后使下标为该值的数组的值为1，接着让以该包裹为下标的数组值为1。如此直至读入所有包裹，最后从dp[箱子的大小]开始找起，找到数组的值不为1的地方跳出。这大概就是所谓的用空间换时间？？ 下面是代码：
#include<iostream>#include<stdio.h>using namespace std;char b[30000]={0};int main(void){ int v,n,a; cin>>v>>n; for(int i=0;i<n;i++) { cin>>a; for(int j=v;j>=0;j--) { if(b[j]==1) b[j+a]=1; } b[a]=1; } for(int i=0;i<=v;i++) { if(b[v-i]==1) { cout<<i<<endl; break; } }}新闻热点
疑难解答
