首页 > 代码库 > 双重背包问题
双重背包问题
题目描述
N个物品，每个物品都有恰好两个。第I种物品的体积和价值分别是WI 和vi。
背包的体积为T，问在不超过背包体积的情况下，最多能放进多少价值的物品。
输入输出格式
输入格式：第一行两个整数N,T。
接下来N行每行两个整数Wi,Vi 。
输出格式：一行一个整数代表答案。
输入输出样例
输入样例#1：
2 31 22 1
输出样例#1：
4
说明
对于100%的数据，1 ≤ 所有变量 ≤ 100,。
%%%%%zhx orz钟长者出的 水题耶
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 5 const int N=1004; 6 struct node{ 7 int num;int wight,vul; 8 }a[N]; 9 int dp[N][N];10 int main()11 {12 int n,m;13 scanf("%d%d",&n,&m);14 for(int i=1;i<=n;i++)15 {16 scanf("%d%d",&a[i].wight,&a[i].vul);17 }18 for(int i=1;i<=n;i++)19 {20 for(int j=0;j<=m;j++)21 {22 for(int q=0;q<=2;q++)23 {24 if(j>=a[i].wight*q)25 {26 dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].wight*q]+a[i].vul*q);27 }28 }29 }30 }31 int ans(0);32 printf("%d",dp[n][m]);33 return 0;34 }
双重背包问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。