南郵 OJ 1308 背包問題

背包問題

時間限制(普通/Java) :  1000 MS/ 3000 MS          運作記憶體限制 : 65536 KByte

總送出 : 82            測試通過 : 31 

比賽描述

         試設計一個用回溯法搜尋子集空間樹的函數。該函數的參數包括結點可行性判定函數和上界函數等必要的函數，并将此函數用于解0-1背包問題。

0-1 背包問題描述如下：給定n 種物品和一個背包。物品i 的重量是 wi ，其價值為 v i，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

在選擇裝入背包的物品時，對每種物品i隻有2 種選擇，即裝入背包或不裝入背包。不能将物品i 裝入背包多次，也不能隻裝入部分的物品i。

0-1 背包問題形式化描述：給定C＞0， Wi ＞0， Vi ＞0，1≤i≤n，要求n 元0-1向量(  x1 ，x2 ，…， xn )，xi∈｛0，1｝，1≤i≤n，使得                  

達到最大

輸入

 第一行有2個正整數n和c。n是物品數，c是背包的容量。接下來的1 行中有n個正整數，表示物品的價值。第3 行中有n個正整數，表示物品的重量。

輸出

 計算出裝入背包物品的最大價值和最優裝入方案。

樣例輸入

5 10

6 3 5 4 6

2 2 6 5 4

樣例輸出

15

1 1 0 0 1

提示

題目來源

算法設計與實驗題解

#include<stdio.h>
#include<stdlib.h>
int f(int c,int n,int *w,int *v,int i,bool *b,bool *mb,int mV){
	if(c<=0 || i==n)
		return mV;
	int p,q;
	b[i]=0;
	p = f(c,n,w,v,i+1,b,mb,mV);
	if(c>w[i]){
		q = f(c-w[i],n,w,v,i+1,b,mb,mV)+v[i];
		if(q>p){
			p=q;
			b[i]=1;
		}
	}
	if(p>mV){
		for(int k=0; k<n; k++)
			mb[i]=b[i];
		mV=p;
	}
	return mV;
}
int main(){
	int n,c,*w,*v,i,mV;
	bool *b,*mb;
	while(scanf("%d%d",&n,&c)==2){
		w=(int*)malloc(sizeof(int)*n);
		v=(int*)malloc(sizeof(int)*n);
		b=(bool*)calloc(n,sizeof(bool));
		mb=(bool*)calloc(n,sizeof(bool));
		for(i=0;i<n;i++)
			scanf("%d",v+i);
		for(i=0;i<n;i++)
			scanf("%d",w+i);
		mV=0;
		mV=f(c,n,w,v,0,b,mb,mV);
		printf("%d\n",mV);
		printf("%d",mb[0]);
		for(i=1;i<n;i++)
			printf(" %d",mb[i]);
		printf("\n");
		free(w);
		free(v);
		free(b);
		free(mb);
	}
}



/*
#include<stdio.h>
#include<stdlib.h>
//c:總容量
//n:物品總個數
//w[i]:第i件物品的重量
//v[i]:第i件物品的價值
//i:目前判斷要不要加入到包中的物品下标
//current:目前的存放下标标記
//maxBits:目前最優值得下标
//maxV:目前的最優值
int findMaxV(int c, int n, int *w, int *v, int i, bool *current, bool *maxBits, int maxV){
	if(c<=0 || i==n){
		return maxV;
	}
	int in,out;
	current[i]=0;
	out = findMaxV(c,n,w,v,i+1,current,maxBits,maxV);
	if(c>w[i]){
		in = findMaxV(c-w[i],n,w,v,i+1,current,maxBits,maxV)+v[i];
		if(in>out){
			out=in;
			current[i]=1;
		}
	}
	if(out>maxV){
		for(int k=0; k<n; k++){
			maxBits[i]=current[i];
		}
		maxV=out;
	}
	return maxV;
}

int main(){
	int n,c,*w,*v,i,maxV;
	bool *current,*maxBits;
	while(scanf("%d%d",&n,&c)==2){
		w=(int*)malloc(sizeof(int)*n);
		v=(int*)malloc(sizeof(int)*n);
		current=(bool*)calloc(n,sizeof(bool));
		maxBits=(bool*)calloc(n,sizeof(bool));
		for(i=0;i<n;i++){
			scanf("%d",v+i);
		}
		for(i=0;i<n;i++){
			scanf("%d",w+i);
		}
		maxV=0;
		maxV=findMaxV(c,n,w,v,0,current,maxBits,maxV);
		printf("%d\n",maxV);
		printf("%d",maxBits[0]);
		for(i=1;i<n;i++){
			printf(" %d",maxBits[i]);
		}
		printf("\n");
		free(w);
		free(v);
		free(current);
		free(maxBits);
	}
}
*/