首页 > 代码库 > 背包问题
背包问题
Problem Description
简单的背包问题。设有一个背包，可以放入的重量为s。现有n(n<=10)件物品，重量分别为w1,w2,...,wn，均为正整数，从n件物品中挑选若干件，使得放入背包的重量之和正好为s。找到一组解即可。如果找不到输出“not found”。
Input
输入有多组数据，每组数据的第1行是物品总件数和背包的载重量，第2行为各物品的重量。
Output
对于每组数据输出各所选物品的序号和重量。
Sample Input
5 101 2 3 4 5
Sample Output
number:1 weight:1number:4 weight:4number:5 weight:5
/* 把所有的重量从小到大排序。每次都是从最大的数开始加 再看前面的数有没有< = 背包重量-已加的重量 有的话再加上*/#include<iostream>#include<cstdio>#include<algorithm>using namespace std;struct st{ int num; //重量 int xu; //序号 } w[15], b[15];bool cmp(st a, st b ){ if(a.num != b.num) return a.num < b.num; else return a.xu < b.xu;}int main(){ int n, s, i, k, j, sum = 0, x, flag = 0, t, m; while(cin >> n >> s) { sum = 0; flag = 0; for(i = 1; i <= n; i++) //赋初值 { cin >> w[i].num; w[i].xu = i; } sort(w + 1, w + n + 1, cmp); // 排序 重量从小到大 for(i = n; i >= 1; i--) // 处理数据，把符合要求的数放在b中 { k = 0; sum = w[i].num; b[k].num = w[i].num; b[k].xu = w[i].xu; x = s - sum; // 差 k++; for(j = i - 1; j > 0; j--) { if(w[j].num <= x) // 当前数是否小于差 { sum += w[j].num; // sum加上当前数 b[k].num = w[j].num; b[k].xu = w[j].xu; x = s - sum; // 差=背包重量-已加的重量 k++; } } // 当有个重量为零时，可加/可不加 if(sum == s&&flag == 0) // flag标记只输出一组 { for(j = 0; j < k - 1; j++) //排序 输出时序号小的在前面 for(t = j + 1; t < k; t++) { if(b[j].xu > b[t].xu) { m = b[j].xu; b[j].xu = b[t].xu; b[t].xu = m; m = b[j].num; b[j].num = b[t].num; b[t].num = m; } } for(j = 0; j < k; j++) printf("number:%d weight:%d\n", b[j].xu, b[j].num); flag=1; } if(i==1&&flag==0) //当只剩下一个数时 && 没有找到 cout << "not found"<< endl; } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。