Bom galera, tô tentando modificar o knapsack com repetições em que os valores dos itens muda de acordo com o uso. Ou seja, os itens têm um fator que usando essa fórmula: f=valorAtual-((x-1)² * fator) altera o valor do item. (x é a quantidade de vezes que o item foi selecionado). O array B carrega os fatores Só que em alguns testes não funcionou, alguém consegue ver algo de errado com o código?
private static int max(int i, int j) {
return (i > j) ? i : j;
}
static class Max{
int dp;
int [] x;
}
static int knapsack(int W, int n, int[] val, int[] wt, int [] B) {
Max dp[] = new Max[W + 1];
int f;
for(int i = 0; i <= W; i++){
dp[i]=new Max();
dp[i].x= new int[n];
for(int j = 0; j < n; j++){
if(wt[j] <= i){
//calcula o novo valor do item
int aux=dp[i-wt[j]].x[j]+1;
int u=((aux-1)*(aux-1));
f=val[j] - ( u * B[j] );
if(f<=0){
f=0;
}
//muda as x vezes que o item foi escolhido
if(dp[i-wt[j]].dp+f>dp[i].dp){
for(int k=0; k<n; k++){
dp[i].x[x]=dp[i-wt[j]].x[x];
}if(f>0){
dp[i].x[j]++;
}
}
//escolhe a maior opcao
dp[i].dp = max(dp[i].dp, dp[i - wt[j]].dp + f);
}
}
}
return dp[W].dp;
}