HDU2191多重背包例題
悼念512汶川大地震遇難同胞——珍惜現在，感恩生活
Time Limit: 1000 MS Memory Limit: 32768 KB
64-bit integer IO format: %I64d , %I64u Java class name: Main
Description
為了挽救災區同胞的生命，心系災區同胞的你準備自己采購一些糧食支援災區，現在假設你一共有資金n元，而市場有m種大米，每種大米都是袋裝產品，其價格不等，并且只能整袋購買。
請問：你用有限的資金最多能采購多少公斤糧食呢？
后記：
人生是一個充滿了變數的生命過程，天災、人禍、病痛是我們生命歷程中不可預知的威脅。
月有陰晴圓缺，人有旦夕禍福，未來對于我們而言是一個未知數。那么，我們要做的就應該是珍惜現在，感恩生活——
感謝父母，他們給予我們生命，撫養我們成人；
感謝老師，他們授給我們知識，教我們做人
感謝朋友，他們讓我們感受到世界的溫暖；
感謝對手，他們令我們不斷進取、努力。
同樣，我們也要感謝痛苦與艱辛帶給我們的財富～
Input
Output
Sample Input
1 8 2 2 100 4 4 100 2
Sample Output
400
題目：有N種物品和一個容量為V的背包。第i種物品最多有num[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝
入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
分析：狀態轉移為：
題目：http://acm.hdu.edu.cn/showproblem.php?pid=2191
- #include <iostream>
- #include <string.h>
- #include <stdio.h>
- using namespace std;
- const int N = 1005;
- int dp[N];
- int c[N],w[N],num[N];
- int n,m;
- void ZeroOne_Pack(int cost,int weight,int n)
- {
- for(int i=n; i>=cost; i--)
- dp[i] = max(dp[i],dp[i-cost] + weight);
- }
- void Complete_Pack(int cost,int weight,int n)
- {
- for(int i=cost; i<=n; i++)
- dp[i] = max(dp[i],dp[i-cost] + weight);
- }
- int Multi_Pack(int c[],int w[],int num[],int n,int m)
- {
- memset(dp,0,sizeof(dp));
- for(int i=1; i<=n; i++)
- {
- if(num[i]*c[i] > m)
- Complete_Pack(c[i],w[i],m);
- else
- {
- int k = 1;
- while(k < num[i])
- {
- ZeroOne_Pack(k*c[i],k*w[i],m);
- num[i] -= k;
- k <<= 1;
- }
- ZeroOne_Pack(num[i]*c[i],num[i]*w[i],m);
- }
- }
- return dp[m];
- }
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- cin>>m>>n;
- for(int i=1; i<=n; i++)
- cin>>c[i]>>w[i]>>num[i];
- cout<<Multi_Pack(c,w,num,n,m)<<endl;
- }
- return 0;
- }
令附加通俗代碼
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int m,n;
int p[105],h[105],c[105];
int dp[105];
void pd1(int cost,int value)//wanquan
{
for(int i=cost;i<=m;i++)
{
dp[i]=max(dp[i],dp[i-cost]+value);
}
}
void pd2(int cost,int value)//01
{
for(int i=m;i>=cost;i--)
{
dp[i]=max(dp[i],dp[i-cost]+value);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(dp,0,sizeof(dp));
memset(p,0,sizeof(p));
memset(h,0,sizeof(h));
memset(c,0,sizeof(c));
scanf("%d%d",&m,&n);
for(int k=1;k<=n;k++)
scanf("%d%d%d",&p[k],&h[k],&c[k]);
for(int i=1;i<=n;i++)
{
if(c[i]*p[i]>m)
{
pd1(p[i],h[i]);
}
else
{
int k=1;
while(k<c[i])
{
pd2(k*p[i],k*h[i]);
c[i]-=k;
k=k*2;
}
pd2(c[i]*p[i],c[i]*h[i]);
}
}
printf("%d\n",dp[m]);
}
return 0;
}
浙公網安備 33010602011771號