c++ dp 贪婪的戈尔曼题解

1、题目：

2、思路：

非常明确的01背包问题可以将条件从大到小遍历 ，但此题难点在于（个人观点）如何选出最小值而不是传统问题的最大值。

3正确代码：

#include <iostream>
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
long long int a[1005][3],dp[55][55]={0},max1=0;//dp的两个参量分别是小狗叫次数和大狗叫次数 
int main(){
	int n,xj,dj,ck1,ck2;//此处设立了两个参量（ck1,ck2）用于状态转移时参数的选用 
	cin>>n>>xj>>dj;
	memset(dp,0x3f3f3f,sizeof(dp));//初始化为无穷大 
	dp[0][0]=0;//显有两只狗叫的次数都为零时 花费为零 
	for(int i=1;i<=n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
		a[i][2]=a[i][2]*2;
	}
	for(int i=1;i<=n;i++){
		for(int j=xj;j>=0;j--){	
			for(int w=dj;w>=0;w--){
				ck1=j+a[i][0];
				ck2=w+a[i][1];
				if(ck1>xj){
					ck1=xj;//超过所需值则按所需值处理 下同（因为两个参量都要达标所以有可能有参量超过所需值此处也是与传统01背包的不同之处） 
				}
				if(ck2>dj){
					ck2=dj;
				}
				dp[ck1][ck2]=min(dp[ck1][ck2],dp[j][w]+a[i][2]);//状态转移 
			}
		}
	}
	cout<<dp[xj][dj]<<endl;
    return 0;
}

 样例数据：

输入：

5 5 10
1 2 5
2 4 10
3 7 8
1 11 36
6 0 18

 输出：

36

错误代码（按照传统01背包问题写的）：

#include <iostream>
#include<bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
    int n,xj,dj;
    long long int a[1005][3],dp[55][55],max1=0;
    cin>>n>>xj>>dj;
    for(int i=1;i<=n;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
        a[i][2]=a[i][2]*2;
        if(max1<a[i][2]) max1=a[i][2];
    }
    for(int i=0;i<=xj;i++){
        for(int j=0;j<=dj;j++){
            dp[i][j]=max1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=xj;j>=a[i][0];j--){    
            for(int w=dj;w>=a[i][1];w--){
                dp[j][w]=min(dp[j][w],dp[j-a[i][0]][w-a[i][1]]+a[i][2]);
                dp[j][w]=min(dp[j][w],dp[j][w-a[i][1]]+a[i][2]);
                dp[j][w]=min(dp[j][w],dp[j-a[i][0]][w]+a[i][2]);
            }
        }
    }
    cout<<dp[xj][dj];
    return 0;
}