背包问题思考

背包问题分类：

1.01背包问题

---

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

第 ii 件物品的体积是 vivi，价值是 wiwi。

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

输入格式

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

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

输出格式

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

数据范围

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

---

//朴素算法
#include

using namespace std ;

const int N = 1010 ;
int dp[N][N] ;
int v[N], w[N] ;

int main(){
    int m, n ; cin>>m >> n ;
    for(int i = 1 ; i<= m ;++i ) cin >> v[i]>>w[i] ;
    
    for(int i = 1 ; i<= m ;++i) {
        for(int j = 0 ; j<= n ;++j){
            dp[i][j] = dp[i-1][j] ;
            if(j>= v[i]) dp[i][j] = max(dp[i-1][j-v[i]]+w[i]) ;
        }
    }
    cout<< dp[m][n]<

//进行优化
#include

using namespace std ;

const int N = 1010 ;

int dp[N] ; int v[N] ; int w[N] ;

int main(){
    int m ,n ; 
    cin>> m >> n ;
    for(int i = 1 ;i<= m; ++i) cin>> v[i]>>w[i] ;
    for(int i = 1; i<= m ;++i )
        for(int j = n ; j>= v[i] ;--j )
            dp[j] = max(dp[j], dp[j-v[i]]+w[i]) ;
    cout<

2.完全背包问题

有 NN 种物品和一个容量是 VV 的背包，每种物品都有无限件可用。

第 ii 种物品的体积是 vivi，价值是 wiwi。

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

输入格式

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

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

输出格式

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

数据范围

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

#这种算法最直观，但是会超时间，此题的数据是在1000 ，这有一个三层循环应该是在10的九次方左右，会超时,所以就有了之后的优化算法
#include

using namespace std ;
const int N = 1010 ;
int f[N][N] ; int v[N] ; int w[N] ;

int main(){
    int m ,n  ;
    cin>>m>>n ;
    for(int i = 1 ; i<= m ;++i) cin>> v[i]>>w[i] ;
    for(int i = 1 ; i<= m ;++i ) {
        for(int j = 0 ; j<= n ;++j){
            f[i][j] = f[i-1][j] ;
            
            for(int k = 1 ; j-k*v[i] >= 0 ; k++){
                f[i][j]  = max(f[i][j] , f[i-1][j-k*v[i]]+k*w[i]) ;
            }
        }
    }
    cout<< f[m][n] <

//朴素算法

#include

using namespace std ;

const int N =  1010 ;

int dp[N][N] ; int v[N]; int w[N] ;

int main(){
    int m , n ;
    cin>>m >>n ;
    for(int i = 1 ;i<= m ;++i) cin>> v[i]>>w[i] ;
    for(int i = 1; i<= m ; ++i) 
        for(int j = 0 ; j<= n ++j){
            dp[i][j] = dp[i-1][j] ;
            if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j-v[i]]+w[i]) ;
        }
    cout<< dp[m][n] <

//优化算法

#include

using namespace std ;

const int N = 1010; 

int dp[N] ; int v[N] ;int w[N] ; 

int main(){
    int m , n ;
    cin>>m >> n ; 
    for(int i =1 ; i <= m ;++i) cin>>v[i]>>w[i] ;
    
    for(int i = 1; i <= m ;++i)
        for(int j = v ; j<= n ;++j)
            dp[j] = max(dp[j], dp[j-v[i]]+w[i]) ;
    
    cout>>dp[n] ;
    return 0 ;
}

3.多重背包问题

有 NN 种物品和一个容量是 VV 的背包。

第 ii 种物品最多有 sisi 件，每件体积是 vivi，价值是 wiwi。

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

输入格式

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

接下来有 NN 行，每行三个整数 vi,wi,sivi,wi,si，用空格隔开，分别表示第 ii 种物品的体积、价值和数量。

输出格式

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

数据范围

0<N,V≤1000<N,V≤100
0<vi,wi,si≤1000<vi,wi,si≤100

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

#这能ac是我妹想到的，总之这是一个最朴素的做法，我估计数据增强之后就不可以了
#include

using namespace std ;

const int N = 1010 ;
int f[N][N] ;
int v[N] ; int w[N] ;int s[N];

int main(){
    int m ,n  ;
    cin>>m >>n ;
    for(int i = 1 ; i<= m ;++i) cin>>v[i]>>w[i]>>s[i] ;
    
    for(int i = 1 ;i<= m ;++i){
        for(int j = 0 ;j<=n ;++j){
            f[i][j] = f[i-1][j] ;
            for(int k = 1 ; k<= s[i]&& j-k*v[i]>= 0 ;++k){
                f[i][j] = max(f[i][j], f[i-1][j-k*v[i]]+k*w[i]) ;
            }
        }
    }
    cout<