当前位置：首页 > article >正文

代码随想录训练营day36|1049.最后一块石头的重量II，494.目标和，474.一和零

article 2024/9/22 6:30:33

1049.最后一块石头的重量II

timu

思路：首先是01背包，因为每块石头只能用一次，（新产生的石头也不是原来的）。背包的体积是石头的总重量。价值是粉碎的石头重量，要想办法让价值最大化，这样剩下来的石头就最轻。dp[i][j]是空间为j时的背包，它可以选择粉碎不粉碎第i块石头，这样它的价值就和dp[i-1][j]一样，也可以选择粉碎：dp[i][j]=dp[i-1][j-2weight[i]]+2weight[i]

草，思路好像错了，应该是把石头分成尽可能重量相接近的两堆，这样就能使得剩余重量最少。

	//j是背包能装的最大重量，dp[i][j]是当前背包实际装的最大重量，
	//最后用sum_weight-2*dp[i-1][m];
	int m=sum/2;
	int n=stones.size()
	//小的那一堆
	vector<vector<int>> dp(n,vector<int>(m+1,0));
	for(int j=nums[0];j<m+1;j++){
		dp[0][j]=nums[0];
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
			if(j-nums[i]>=0)
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	return sum_weight-2*dp[stones.size()-1][sum_weight/2];

494.目标和

题目

思路我一开始想的还是对的，就是找（sum-target）/2的数组，但是我在dp[i][j]的含义上没定义好，我定义的仍然是当前最大的重量，但应该是能装满当前j空间的方法数。

dp[i][j]要想装满只有两种方法，要么不装nums[i]，这样它的方法数就等于dp[i-1][j]
要么装上nums[i]，这样就要把j-nums[i]的空间填满，所以
dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];

本题的另一个难点在于如何初始化，首先dp[0][0]应该初始化为1，因为对于容量为0的背包什么都不做就能把它装满，然后dp[0][nums[0]]=1

只有它能恰好用nums[0]装满
然后就是第0列的初始化，应该统计0，i之间有几个0，因为只要有n个0，就有pow(2，n)种办法，既可以填+也能填-。

		for(int j=1;j<target_2+1;j++){
		            if(j==nums[0]){
		                dp[0][j]=1;
		                break;
		            }
		}
        dp[0][0]=1;
        int numZero = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) numZero++;
            dp[i][0] = (int) pow(2.0, numZero);
        }
        //装满空间为0的背包什么都不用做
        for(int i=1;i<n;i++){
            for(int j=1;j<target_2+1;j++){
                if(j-nums[i]>=0)
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        return dp[n-1][target_2];

如果用一维数组的话，在nums[0]==0时，也要dp[0]=2；

一和0

题目
题目要求有最多m个0和n个1，那它就有两个维度了，
之前只有一个比较维度是可以用滚动数组实现，现在要用二维数组
dp[i][j]中的i是最多有多少个i个0，j是最多有j个1，dp[i][j]的含义是当前条件下最长的子集数量（value）
假设当前子串有x个0，y个1
则dp[i][j]=max（dp[i-x][j-y]+1，dp[i][j]）;
可以类比纯01背包中dp[j]=max（dp[j]，dp[j-weight[i]]+value[i]）;
只不过这里每个的value都是1.

先遍历物品，再遍历背包，需要注意的是背包需要倒叙遍历，这样才能确保每个物品只用了一次。
(正序的话do[i-x][j-y]取的最长子集有可能就是包含了放入x和y的情况，会重复)

		 vector<vector<int>> dp(m+1,vector<int> (n+1,0));
        //m=1时需要0，1两种选择。
        dp[0][0]=0;
        for(int str=0;str<strs.size();str++){
            string s=strs[str];
            int x=0,y=0;
            for(char a:s){
                if(a=='0')
                    x++;
                else
                    y++;
            }
            for(int i=m;i>=x;i--){
                for(int j=n;j>=y;j--){
                    dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1);
                    
                
                }
            }
           
        }
        return dp[m][n];