首页 > ACM题库 > HDU-杭电 > HDU 1711 Number Sequence-背包问题-[解题报告] C++
2013
12-21

HDU 1711 Number Sequence-背包问题-[解题报告] C++

Number Sequence

问题描述 :

Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], …… , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

输入:

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N]. The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000].

输出:

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

样例输入:

2
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 1 3
13 5
1 2 1 2 3 1 2 3 1 3 2 1 2
1 2 3 2 1

样例输出:

6
-1

题目大意:说的是杭电以前分家的时候,财产要尽可能的均匀分给两个兄弟。现在告诉你价值为n的物品有m件,你的任务就是把这些东西尽可能的分成两份。然后输出最后每家分的的财产总和。最大的总在最前面········

这一道题只要理解01背包、完全背包、多重背包,就很快可以做出来。

/*
 * 1711_2.cpp
 *
 *  Created on: 2013年7月30日
 *      Author: Administrator
 */

#include <stdio.h>
#include <string.h>
#define N 50
//int max(int a , int b){
//	return (a>b)?a:b;
//}
//
//int min(int a ,int b){
//	return (a>b)?b:a;
//}
int max(int a ,int b){
	return (a > b)?a:b;
}

int min(int a ,int b){
	return (a > b)?b:a;
}

int f[N*N*N + 5],c[N+5],amount[N+5],V ;

void ZeroOnePack(int cost,int weight)
{
	int j;
	for(j=V;j>=cost;j--){
		f[j]=max(f[j],f[j-cost]+weight);
	}
}


void CompletePack(int cost , int weight){
	int v;
	for( v = cost ; v <=V  ; v++){//不要写成v--,否则会造成程序异常终止。而且很难调
		f[v] = max(f[v],f[v-cost] + weight);
	}

}
void MultiplePack(int cost ,int weight , int amount){
	if(cost*amount >= V){
		CompletePack(cost,weight);
		return ;
	}
	int k = 1;
	while( k < amount){
		ZeroOnePack(k*cost,k*weight);
		amount -= k;
		k=k*2;
	}
	ZeroOnePack(amount*cost,amount*weight);
}



int main(){

	int i,n,sum ;

	while(scanf("%d",&n),n >= 0){

		 sum = 0;
		for( i = 0 ; i < n ; ++i){
			scanf("%d%d",&c[i],&amount[i]);

			sum +=  c[i]*amount[i];
		}

		V = sum/2;
		memset(f,0,sizeof(f));

		for( i = 0 ; i < n ; ++i ){
			MultiplePack(c[i],c[i],amount[i]);

		}
		printf("%d %d\n",max(f[V],sum-f[V]),min(f[V],sum - f[V]));



	}
	return 0;
}

解题报告转自:http://blog.csdn.net/hjd_love_zzt/article/details/9630949


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3