Backpack problem

/*
一共有n件物品，背包容量为m，每件物品有体积weight 和value，求背包可以装的最大价值。

01背包是最简单的背包问题，每件物品只有选与不选两种情况：

dp[i][j] :表示选第i件物品时重量为j的最大价值。
1.不选第i件物品
dp[i][j] = dp[i-1][j]
2.选第i件物品的最大值（背包容量足够）
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])

*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010;
int dp[N][N],weight[N],value[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i =1;i<=n;++i)
    {
        cin>>weight[i]>>value[i];
    }
    for(int i =1;i<=n;++i)
    {
        for(int j =0;j<=m;++j)
        {
            dp[i][j] = dp[i-1][j];
            if(j>=weight[i])
            {
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i]);
            }
        }
    }
    /*
    一维优化
    int dp[N];
    for(int i=1;i<=n;++i)
    {
    	for(int j =m;j>=weight[i];--j)
    	{
    		dp[j] = max(dp[j],dp[j-weight[i]] + value[i]);
    	}
    }
    ans = dp[m];
    */
    int ans = dp[n][m];
    cout<<ans<<endl;
    system("pause");
    return 0;
}
// 练习1 HDU2602 HDU2546,HDU2955,HDU1203,HDU1171,HDU2639,
// 练习2 https://www.acwing.com/problem/content/2/

/*
完全背包与01背包的区别是每件物品有无限个，每件物品可以去N件；
for(int i =1;i<=n;++i)
{
	for(int j =m;j>=weight[i];--j)
	{
        for(int k =0;k*weight[i]<=j;++k)
        {
            dp[j] = max(dp[j],dp[j-k*weight[i]]+k*value[i]);
        }
	}
}
优化之后变为：
for(int i =1;i<=n;++i)
{
	for(int j =weight[i];j<=m;++j)
	{
		dp[j] = max(dp[j],dp[j-weight[i]] + value[i]);
		
	}
}
*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010;
int dp[N],weight[N],value[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i =1;i<=n;++i)
    {
        cin>>weight[i]>>value[i];
    }
    for(int i =1;i<=n;++i)
    {
        for(int j =weight[i];j<=m;++m)
        {
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    int ans = dp[m];
    cout<<ans<<endl;
    return 0;
}
//练习https://www.acwing.com/problem/content/3/
//

/*
多重背包与上述背包的区别是，每件物品只有有限个，拿取的数量有限。
*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 110;
int n,m;
int dp[N];
int w[N],v[N],s[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>w[i]>>v[i]>>s[i];
    }
    for(int i=1;i<=n;++i)
    {
        for(int j = m ;j>=0;--j)
        {
            for(int k= 1;k<=s[i]&&k*w[i]<=j;++k)
            {
                dp[j] = max(dp[j],dp[j-k*w[i]]+ k*v[i] ) ;
            }
        }
    }
    int ans = dp[m];
    cout<<ans<<endl;
    system("pause");
    return 0;
}
// 练习 https://www.acwing.com/problem/content/4/

//二进制优化
/*
多重背包与上述背包的区别是，每件物品只有有限个，拿取的数量有限。
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
const int N = 2200;
int n,m;
int dp[N];
int w[N],v[N],s[N];
struct good
{
    int w,v;
};
int main()
{
    cin>>n>>m;
    vector<good> goods;
    for(int i=1;i<=n;++i)
    {
        int w,v,s;
        cin>>w>>v>>s;
        for(int k=1;k<=s;k*=2)
        {
            s-=k;
            goods.push_back({w*k,v*k});
        }
        if(s>0) goods.push_back({w*s,v*s});
    }
    for(auto it = goods.begin();it!=goods.end();++it)
    {
        for(int j = m ;j>=it->w;--j)
        {
            
                dp[j] = max(dp[j],dp[j-it->w]+ it->v ) ;
            
        }
    }
    int ans = dp[m];
    cout<<ans<<endl;
    system("pause");
    return 0;
}
// 练习 https://www.acwing.com/problem/content/4/

/*
混合背包是每件物品分为三类:
1.只有拿与不拿两种状态
2.有无数件
3.件数有限制
混合背包问题分组解决子问题
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int N = 1010;

struct Thing
{
    int kind;
    int w,v;
} ;
int dp[N];
int main()
{
    vector<Thing > thing;
    int n,m;
    cin>>n>>m;
    for(int i =1;i<=n;++i)
    {
        int v,w,s;
        cin>>w>>v>>s;
        if(s<0)
            thing.push_back({-1,w,v});
        else if(s==0) 
            thing.push_back({0,w,v});
        else
        {
            for(int k=1;k<=s;k*=2)
            {
                s-=k;
                thing.push_back({-1,w*k,v*k});
            }
            if(s>0)
                thing.push_back({-1,s*w,s*v});
        }
    }
    for(auto it = thing.begin();it!=thing.end();++it)
    {
        if(it->kind < 0)
        {
            for(int j=m;j>=it->w;j--)
            {
                dp[j] = max(dp[j],dp[j-it->w]+it->v);
            }
        }
        else
        {
            for(int j =it->w;j<=m;++j)
            {
                dp[j] = max(dp[j],dp[j-it->w]+it->v);
            }
        }
        
    }

    
    cout<<dp[m]<<endl;
    system("pause");
    return 0;
}