优化Knapsack解决方案的空间复杂度

Question

下面是使用自底向上方法的典型背包工作解决方案。如何优化它的空间复杂度？ 目前空间复杂度为0(行*列)

 int val[] = new int[] { 60, 100, 120 };
            int wt[] = new int[] { 10, 20, 30 };
            int capacity= 50; //capacity of knapsack
            int n = val.length;
            System.out.println(knapsack(capacity, wt, val, n)); //220

public static int knapsack(int c, int wt[], int val[], int n) {
        
        int dp[][] = new int[n+1][c+1];
        
        for( int i =0 ;i < n+1;i++)
            for( int j =0 ;j < c+1;j++)
              if( i==0 || j==0 )
                  dp[i][j]=0;
        
        
        for( int i =1;i < n+1;i++)
        {
            for( int j =1 ;j < c + 1;j++)
            {
                
                if ( wt[i-1] <= j)
                {
                    dp[i][j] = Math.max(val[i-1]+ dp[i-1][j-wt[i-1]] , dp[i-1][j]);
                } else 
                {
                    dp[i][j] = dp[i-1][j];
                }
            }
        
        }
        
        return dp[n][c];

    
    }

Answer 1

你可以只用一维 dp 数组来计算它，制作大小为 W 的 dp 数组，在计算结束时 dp[W] 将存储计算后的结果，下面是 c++ 中的代码:-

int 背包(int c, int wt[], int val[], int n){

    vector<int> dp(W+1, 0);
    
    for(int i=0;i<n;i++){
        
        for(int j=W; j>=wt[i]; j--){
            
            dp[j] = max(dp[j], val[i] + dp[j-wt[i]]);
        }
    }
    return dp[W];

}