Sippert, Tiago A. S.

Algoritmo de Maratona de Programação utilizando programação dinâmica.

#include <iostream>
using namespace std;
int w=10,n;
int peso[1001];
int valor[1001];
int t[1001][11];

void mochila(){
	int a,b;
	for(int y=0;y<=w;y++){
		t[0][y]=0;
		for(int i=1;i<=n;i++){
			a=t[i-1][y];
			if(peso[i] > y)
				b=0;
			else
				b=t[i-1][y-peso[i]] + valor[i];
			if(a>b)
				t[i][y]=a;
			else
				t[i][y]=b;
		}
	}
}
int main(){
	int l=1;
	while((cin>>n)&&(n!=0)){
		for(int i=1;i<=n;i++){
			cin >> valor[i];
			cin >> peso[i];
		}
		mochila();

		int x[n+1];
		//for(int i=1;i<=n;i++)	x[i]=0;
		memset(x,0,sizeof(x));
		int waux=w;
		for(int i=n;i>=1;i--){
			if(t[i][waux] == t[i-1][waux])
				x[i]=0;
			else{
				x[i]=1;
				waux=waux-peso[i];
			}
		}
		int ganho=0;
		for(int i=1;i<=n;i++){
			if(x[i]==1)
				ganho += valor[i];
		}
		cout << "Instancia "<< l++ << endl << ganho << endl << endl;
	}
	return 0;
}

Posts relacionados:

1. Algoritmo: O imperador Lu Zhin Du
2. Algoritmo: Ajudando a prefeitura
3. Algoritmo: Números de Ka Fu
4. Algoritmo 3n+1 (Maratona de Programação)
5. Métodos de Gauss-Seidel e Gauss-Jacobi

Tags: algoritmos, programacao dinamica