亲宝软件园·资讯

展开

《算法十一》(背包问题)

喵喵与呱呱 人气:1

问题描述:

 

2.问题分析:可以知道满足一个递归式

定义:B(i, j):i代表还有几件商品可以偷

          j代表还剩下的背包空间是多少

 

 例如:

  如果是B(4,20)代表:有4件商品可以偷取,背包剩余空间还有20———>一系列计算————>26

 

 3.定义B数组:

 

4.代码演示: 

#include <iostream>
#include <iomanip> 
#include <math.h>
#include <string.h>
#define N 6 
#define W 21 
using namespace std;
//B[i][j]:i代表还有几件商品可以偷
//		  j代表还剩下的背包空间是多少 
int B[N][W] = {0};
int w[6] = {0, 2, 3, 4, 5, 9};//重量 
int v[6] = {0, 3, 4, 5, 8, 10};//价值

void beibao(){
	int k, c;
	for(k=1; k<N; k++){//5个商品 
		for(c=1; c<W; c++){
			if(w[k]>c){//第k件商品太重超过了背包空间c,不偷 
				B[k][c] = B[k-1][c];
			}else{
				//偷第k件商品 
				int value1 = B[k-1][c-w[k]] + v[k];
				//不偷第k件商品 
				int value2 = B[k-1][c];
				B[k][c] = value1 >= value2 ? value1:value2;
			} 
		}
	}
}

int main(void){
	beibao();
	cout << B[5][20] << endl;
	return 0;
} 

加载全部内容

相关教程
猜你喜欢
用户评论