多重背包

标签：多重 背包 int ij 物品 101 dp

#include<iostream>//01背包问题状态转移方程dp[i][j]=max(dp[i-1 ][j],dp[i-1][j-w[i]]+p[i])区别:因为物品只能装一次所以在比较装入物品后的价值时使用i-1而不是i因为物品只能装一次 
using namespace std;
int main(){
    int dp[101][101]={}; 
    int n,c;//物品种类数,背包容量 
    int w[101]={};//重量 
    int p[101]={};//价值 
    int k[101]={};//数量 
    cin>>n>>c;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>p[i]>>k[i]; 
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=c;j++){
            dp[i][j]=dp[i-1][j];//不放入 
            for(int ij=1;ij<=k[i];ij++){//各种数量的情况 
                if(j>=ij*w[i]){//当容量大于数量*重量时比较不放入和放入谁最优 
                    dp[i][j]=max(dp[i][j],dp[i-1][j-ij*w[i]]+ij*p[i]);//状态转移方程 'dp[i][j]'15行已考虑全部不放入的情况，但是多重背包会多次放数量不同的物品所以当ij=1且dp[i-1][j-ij*w[i]]+ij*p[i]>dp[i-1][j]时最优选择不为dp[i-1][j]然而还要考虑i=2,i=3......所以此时要和dp[i][j]比较
                    cout<<dp[i][j]<<endl;
                }
            }
        }
    }
    cout<<dp[n][c]<<endl;//最终值 
    return 0;
}
/*3 13
2 4 8
3 7 2
4 10 1

29
*/

 

#include<iostream>//01背包问题状态转移方程dp[i][j]=max(dp[i-1 ][j],dp[i-1][j-w[i]]+p[i])区别:因为物品只能装一次所以在比较装入物品后的价值时使用i-1而不是i因为物品只能装一次 using namespace std;int main(){    int dp[101][101]={};     int n,c;//物品种类数,背包容量     int w[101]={};//重量     int p[101]={};//价值 int k[101]={};//数量     cin>>n>>c;    for(int i=1;i<=n;i++){        cin>>w[i]>>p[i]>>k[i];     }     for(int i=1;i<=n;i++){        for(int j=1;j<=c;j++){            dp[i][j]=dp[i-1][j];//不放入             for(int ij=1;ij<=k[i];ij++){//各种数量的情况             if(j>=ij*w[i]){//当容量大于数量*重量时比较不放入和放入谁最优                 dp[i][j]=max(dp[i][j],dp[i-1][j-ij*w[i]]+ij*p[i]);//状态转移方程 'dp[i][j]'15行已考虑全部不放入的情况，但是多重背包会多次放数量不同的物品所以当ij=1且dp[i-1][j-ij*w[i]]+ij*p[i]>dp[i-1][j]时最优选择不为dp[i-1][j]然而还要考虑i=2,i=3......所以此时要和dp[i][j]比较cout<<dp[i][j]<<endl;}        }}    }    cout<<dp[n][c]<<endl;//最终值     return 0;}/*3 132 4 83 7 24 10 1
29*/

标签：多重,背包,int,ij,物品,101,dp
From： https://www.cnblogs.com/AndyYuan/p/16607453.html