有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; } }}新聞熱點
疑難解答
