Вам даны веса и стоимости N предметов, положите эти предметы в рюкзак вместимостью W, чтобы получить максимальную общую стоимость в рюкзаке. Обратите внимание, что у нас есть только одно количество каждого предмета.
Другими словами, даны два целочисленных массива val[0..N-1] и wt[0..N-1], которые представляют значения и веса, связанные с N предметами соответственно. Также дано целое число W, которое представляет вместимость ранца, найдите максимальное подмножество значений из val[], такое, что сумма весов этого подмножества меньше или равна W. Вы не можете разбить элемент, либо выбирайте полный элемент, либо не выбирайте его (свойство 0-1).
Пример 1:
Input:
N = 3
W = 4
values[] = {1,2,3}
weight[] = {4,5,1}
Output: 3
Решение:
class Solution
{
//Function to return max value that can be put in knapsack of capacity W.
static int knapSack(int W, int wt[], int val[], int n)
{
// your code here
//This is similar to subset sum equals to target
// this can be solved using backtracking
//i.e taking value at an index, or not taking it
//lets optimize it with dp
int dp[][] = new int[n][W+1];
for(int row[]: dp){
Arrays.fill(row,-1);
}
return solve(n-1,wt,val,W,dp); // starting from the last index hence n-1;
}
public static int solve(int index, int[] w, int [] val, int target,int dp[][]){
// base case
if(index==0){
//we have reached the first index, and in order for the value to be accepted
//at this index, the weight of the value at i should be equal to target
if(w[index]<=target) return val[index];
return 0;
}
if(dp[index][target]!=-1) return dp[index][target];
int take = 0;
if(target>=w[index]){
take = val[index]+ solve(index-1,w,val,target-w[index],dp);
}
int dontTake = 0+ solve(index-1,w,val,target,dp);
return dp[index][target] = Integer.max(take,dontTake);
}
}
Удаление стекового пространства O(n), т.е. для n раз будет создан стек в худшем случае
Используя подход табуляции (сверху вниз dp)
//tabulation appraoch : dp top down : tc O(n*W) space complexity : O(n*W) on stack space :)
class Solution
{
//Function to return max value that can be put in knapsack of capacity W.
static int knapSack(int W, int wt[], int val[], int n)
{
// your code here
//This is similar to subset sum equals to target
// this can be solved using backtracking
//i.e taking value at an index, or not taking it
//lets optimize it with dp
int dp[][] = new int[n][W+1];
for(int i = wt[0];i<=W;i++){
//it means that weight at index 0 should be less than or equals to
// target ie weigth W
//so every time when the weigth is less than or equals to target(W) strore val[0] in dp[0][i] ;
dp[0][i] = val[0];
}
for(int i =1;i<n;i++){
for(int tar = 0;tar<=W;tar++){
int take =0;
if(tar>=wt[i]){
take = val[i]+dp[i-1][tar-wt[i]];
}
int dontTake = 0+ dp[i-1][tar];
dp[i][tar] = Integer.max(take,dontTake);
}
}
return dp[n-1][W];
}
Неограниченный рюкзак 0/1
Примечание: Каждый элемент может быть взят любое количество раз.
class Solution{
static int knapSack(int N, int W, int val[], int wt[])
{
int dp[][] = new int[N][W+1];
for(int row[]:dp){
Arrays.fill(row,-1);
}
return maxProfit(N-1,W,val,wt,dp);
}
public static int maxProfit(int index, int W,int [] val, int w[],int dp[][]){
if(index==0){
//let say at index 0 val = 10 , w[index] = 3 and W =8 ,
// now we can consider index 0 twice ,as 3*2 =6<=8
///hence for twice 2*val = 2*10 = 20 , hence return 20;
//just convert the above logic in code;
return (W/w[index])*val[index];
}
if(dp[index][W]!=-1) return dp[index][W];
int take =0;// taki
ng the same index
if(W>=w[index]){
take = val[index] + maxProfit(index,W-w[index],val,w,dp);
}
int dontTake = 0 + maxProfit(index-1,W,val,w,dp);
return dp[index][W] = Integer.max(take,dontTake);
}
}