0 / 1背包问题
题目描述
小明就要去春游了，小明的妈妈给他买了很多好吃的，小明想把这些吃的都放进他的书包，但他很快发现，妈妈买的东西实在太多了，他必须放弃一些，但小明又希望能带尽可能多的好吃的。因此小明想请你帮他往书包里装尽可能多的好吃的。
现在我们知道小明的书包最多可以装入总重量为s的物品，同时我们也知道小明妈妈给他买的每样东西的重量，现在请你从这些好吃的中选出若干装入书包中，使得装入物品的总重量正好为s。找到一组解即可。
输入
输入共两行，第一行包含两个正整数k（1<=k<=100）和s（1<=s<=10000），分别代表有k件物品和书包的最大承重s；第二行包含k个正整数，代表每件物品的重量Wi（1<=Wi<=1000）。所有的数字之间用空格隔开。
输出
输出共一行，包含有若干个用空格隔开的正整数，代表被放入书包的若干物品各自的重量（最后一个数据后无多余空格）；若无可行解则输出“No Answer!”。
样例输入
样例1： 8 14 1 3 2 5 9 4 7 6
样例2： 3 12 2 8 5
样例输出
样例1： 1 3 4 6
样例2： No Answer!
代码
。。。打完才发现要输出方案。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include<iostream> #include<cstring> using namespace std; int k,s; int a[1001],f[10001]; int main() { memset(f,-1,sizeof(f)); f[0]=0; cin>>k>>s; for(int i=0;i<=k;i++) cin>>a[i]; for(int i=1;i<=k;i++) for(int v=s;v>=0;v--) if(f[v]>=0&&v+a[i]<=s)f[v+a[i]]=max(f[v]+1,f[v+a[i]]); if(f[s]==-1)cout<<"No Answer!"; //system("pause"); return 0; } |
要方案的话应该是搜索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> #include<cstring> using namespace std; int k,s; int ans=0; int a[101],f[10001],used[101]; void print(int n) { int tot=0; for(int i=1;i<=k;i++) { if(used[i]) { cout<<a[i]; tot++; if(tot!=n)cout<<' '; } } } void search(int t,int v,int l) { if(v>s||ans)return; if(v==s){print(t);ans=1;} else for(int i=l;i<=k;i++) { used[i]=1; search(t+1,v+a[i],i+1); used[i]=0; } } int main() { memset(f,-1,sizeof(f)); memset(used,0,sizeof(used)); f[0]=0; cin>>k>>s; for(int i=1;i<=k;i++) cin>>a[i]; search(0,0,1); if(!ans)cout<<"No Answer!"; return 0; } |
我觉得小明想请你帮他往书包里装尽可能多的好吃的应该是说吃的东西种类也要最多啊。。
好吧我多想了么。。
那就是把背包加上搜素。。大概是下面这样
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<cstring> using namespace std; int k,s; int ans=0; int a[101],f[10001],used[101]; void print() { int tot=0; for(int i=1;i<=k;i++) { if(used[i]) { cout<<a[i]; tot++; if(tot!=f[s])cout<<' '; } } } void search(int t,int v,int l) { if(t>f[s]||v>s||ans)return; if(t==f[s]&&v==s){print();ans=1;} else for(int i=l;i<=k;i++) { used[i]=1; search(t+1,v+a[i],i+1); used[i]=0; } } int main() { memset(f,-1,sizeof(f)); memset(used,0,sizeof(used)); f[0]=0; cin>>k>>s; for(int i=1;i<=k;i++) cin>>a[i]; for(int i=1;i<=k;i++) for(int v=s;v>=0;v--) if(f[v]>=0&&v+a[i]<=s)f[v+a[i]]=max(f[v]+1,f[v+a[i]]); if(f[s]==-1)cout<<"No Answer!"; else search(0,0,1); return 0; } |
Subscribe
计数器 9322788
OI 课件=>
OI 课件=>