代码随想录Day42 | 01背包问题| 416. 分割等和子集

01背包问题（Acwing）

        

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

代码（二维）：

         

#include
using namespace std;
const int N = 1100;
int n,v;
int v1[N];
int w[N];
 
int f[N][N];
 
int main()
{
    cin >> n>>v;
    for (int i = 1; i <= n; i ++ ){
        cin>>v1[i];
        cin>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=v;j++){
            for(int k=0;k<=1;k++){   //每件物品最多取几次，k就设定为几次
                if(j>=k*v1[i])    //能装下k个该物品
                f[i][j]=max(f[i][j],f[i-1][j-k*v1[i]]+k*w[i]);
            }
        }
    }
    cout<
}

   代码（一维）：

#include
using namespace std;
const int N = 1100;
int n,v;
int v1[N];
int w[N];
 
int f[N];
 
int main()
{
    cin >> n>>v;
    for (int i = 1; i <= n; i ++ ){
        cin>>v1[i];
        cin>>w[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=v;j>=0;j--){   //一维数组存储需要倒序，防止被“污染”
            for(int k=0;k<=1;k++){   //每件物品最多取几次，k就设定为几次
                if(j>=k*v1[i])    //能装下k个该物品
                f[j]=max(f[j],f[j-k*v1[i]]+k*w[i]);
            }
        }
    }
    cout<
}

        我编写的是通用的模板，如果每件物品限定了使用次数的时候，修改k的限制即可。

416. 分割等和子集

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        int n=nums.size();
        for(int i=0;i
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        int target = sum/2;
        int f[20010]={0};
        for(int i=0;isize();i++){
            for(int j=target;j>=nums[i];j--){
                f[j] = max(f[j],f[j-nums[i]]+nums[i]);
            }
        }
        if(f[target]==target) return true;
        else return false;
    }
};