代碼：

#include<iostream>
using namespace std;
?
int sum_v;//貨物總價值
int sum_w;//貨物總重量
int goodNum;//一共有多少貨物
int ans;//背包中現(xiàn)有幾個貨物
int maxWeight;//背包的總?cè)萘?br /> int r[100];//記錄最后的選擇的貨物標(biāo)號
?
using namespace std;
struct good
{
? ? int weight;
? ? int value;
? ? int flag;//記錄該貨物是否被挑選
}goods[100];
//更新序列，并返回最大
int record(int sum_v)
{
? ? int count_good = 0;
? ? r[0] = sum_v;
? ? for(int i = 1;i <= goodNum;i++)
? ? {
? ? ? ? if(goods[i].flag == 1)
? ? ? ? {
? ? ? ? ? ? r[++count_good] = i;
? ? ? ? }
? ? }
? ? return count_good;
}
void findMin(int x)
{
? ? if(sum_w > maxWeight)
? ? {
? ? ? ? return;
? ? }
? ? //最好在此處判斷sun_v是否為最大，這樣才不會有sum_w > maxWeight的情況
? ? if(sum_v > r[0])
? ? {
? ? ? ? ans = record(sum_v);
? ? }
? ? //注意此處循環(huán)的條件
? ? for(int i = x;i < goodNum;i++)
? ? {
? ? ? ? sum_w += goods[i].weight;
? ? ? ? sum_v += goods[i].value;
? ? ? ? goods[i].flag = 1;
? ? ? ? findMin(i + 1);
? ? ? ? sum_w -= goods[i].weight;
? ? ? ? sum_v -= goods[i].value;
? ? ? ? goods[i].flag = 0;
? ? }
}
?
int main()
{
?? ?cout<<"請輸入物件的個數(shù)和背包容量：";?
? ? cin >> goodNum >> maxWeight;
? ? for(int i = 1;i <= goodNum;i++)
? ? {
? ? ? ? goods[i].flag = 0;
? ? ? ? cout<<"第"<<i<<"個物品的重量和價值為：";?
? ? ? ? cin >> goods[i].weight >> goods[i].value;
? ? }
? ? findMin(0);
? ? cout<<"背包內(nèi)的物品組合為：";?
? ? for(int i = 1;i <= ans;i++)
? ? {
? ? ? ? cout << r[i] << " ";
? ? }
? ? cout<<endl;
? ? cout << "maxValue：" << r[0] << endl;
? ? return 0;
}

總結(jié)

以上是生活随笔為你收集整理的c语言蛮力法实现背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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