#include <iostream> #include <cstdlib> using namespace std; int N,S; int W[40];// 初始化每個物品的重量 int flag[40]={0};// 標(biāo)記數(shù)組void Print()// 打印結(jié)果 {for(int i=0;i!=N;i++)if (1 == flag[i])cout<<W[i]<<" ";cout<<endl;exit(0); }int main() {freopen("Backpack.in","r",stdin);freopen("Backpack.out","w",stdout); int sum,all_count=1; cin>>S>>N;for(int i=0;i<N;i++)cin>>W[i];for (int i=0;i!=N;i++)// 計(jì)算所有可能性次數(shù),即2的n次方all_count*=2;for(int num=0;num<=all_count;++num){for (int i=0;i!=N;i++)//列舉所有flag數(shù)組可能{if ( flag[i]==0 ){flag[i]=1;continue;}else {flag[i]=0;break;}}sum=0;//本次重量初始化為0for (int i=0;i!=N;i++)//按標(biāo)記計(jì)算所有選中物品重量和if (flag[i]==1)sum+=W[i];if (sum == S)//打印方案 Print(); } cout<<"Failed!\n"; return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的普通背包问题-枚举算法（《算法竞赛宝典》 第二部 基础算法艺术）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。