回溯法解决0-1背包代码,C代码库,德仔网

代码语言

代码分类

【C】回溯法解决0-1背包

作者:weinee / 发布于2015/5/19/ 643


	#include <iostream>
	using namespace std;
	
	bool check(int s[], int C, int k, int x[]){
	 int sum = 0;
	 for(int i=0; i<=k; i++){
	 if(x[i] == 1)
	 sum += s[i];
	 }
	 if(sum > C)
	 return false;
	 else
	 return true;
	
	}
	void KNAPSACK(int v[], int s[], int C, int n){
	 int x[5] = {-1, -1, -1, -1, -1}, X[5] = {0};
	 int k = 0;
	 int V = 0, sum = 0;//总价值
	 while(k>-1){
	 while(x[k] < 1){
	 x[k]++;
	 if(check(s, C, k, x)==true && k==n-1){
	 for(int i=0; i<n; i++){
	 if(x[i] == 1)
	 sum += v[i];
	 }
	 if(V < sum){
	 for(int i=0; i<n; i++)
	 X[i] = x[i];
	 V = sum;
	 sum = 0;
	 }
	 }
	 else if(check(s, C, k, x)==true){
	 k++;
	 }
	 }
	 x[k] = -1;
	 k--;
	 }
	 int temp=0, temp1=0;
	 cout << "选择";
	 for(int i=0; i<n; i++){
	 if(X[i] == 1){
	 temp += v[i];
	 temp1 += s[i];
	 cout << "第" << i+1 << "项，";
	 }
	 }
	 cout << "物品放入背包，物品总体积为" << temp1 << ",总价值为" << temp << "。" << endl;
	}
	int main(int argc, char** argv) {
	 int s[] = {3,5,7,8,9};
	 int v[] = {4,6,7,9,10};
	 KNAPSACK(v, s, 11, 5);
	 return 0;
	}

	

	

	#include <iostream>
	using namespace std;
	
	bool check(int s[], int C, int k, int x[]){
	 int sum = 0;
	 for(int i=0; i<=k; i++){
	 if(x[i] == 1)
	 sum += s[i];
	 }
	 if(sum > C)
	 return false;
	 else
	 return true;
	
	}
	void KNAPSACK(int v[], int s[], int C, int n){
	 int x[5] = {-1, -1, -1, -1, -1}, X[5] = {0};
	 int k = 0;
	 int V = 0, sum = 0;//总价值
	 while(k>-1){
	 while(x[k] < 1){
	 x[k]++;
	 if(check(s, C, k, x)==true && k==n-1){
	 for(int i=0; i<n; i++){
	 if(x[i] == 1)
	 sum += v[i];
	 }
	 if(V < sum){
	 for(int i=0; i<n; i++)
	 X[i] = x[i];
	 V = sum;
	 sum = 0;
	 }
	 }
	 else if(check(s, C, k, x)==true){
	 k++;
	 }
	 }
	 x[k] = -1;
	 k--;
	 }
	 int temp=0, temp1=0;
	 cout << "选择";
	 for(int i=0; i<n; i++){
	 if(X[i] == 1){
	 temp += v[i];
	 temp1 += s[i];
	 cout << "第" << i+1 << "项，";
	 }
	 }
	 cout << "物品放入背包，物品总体积为" << temp1 << ",总价值为" << temp << "。" << endl;
	}
	int main(int argc, char** argv) {
	 int s[] = {3,5,7,8,9};
	 int v[] = {4,6,7,9,10};
	 KNAPSACK(v, s, 11, 5);
	 return 0;
	}

试试其它关键字

　回溯法　　 0-1　　背包　

同语言下

可能有用的

weinee贡献的其它代码(4)