桂林建网站东莞推广系统

01背包问题（Acwing）

        

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

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

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

输入格式

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

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

输出格式

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

代码（二维）：

#include<bits/stdc++.h>
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<<f[n][v];
}

   代码（一维）：

#include<bits/stdc++.h>
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<<f[v];
}

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

416. 分割等和子集

class Solution {
public:bool canPartition(vector<int>& nums) {int sum=0;int n=nums.size();for(int i=0;i<n;i++){sum+=nums[i];}if(sum%2==1) return false;int target = sum/2;int f[20010]={0};for(int i=0;i<nums.size();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;}
};